C++中缀表达式转后缀表达式(求值)

本文主要是介绍C++中缀表达式转后缀表达式(求值)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

菜鸟生成记(79)

输入:变量名(单个字符)和变量值

再输入中缀表达式,然后求值

输入
a 1
b 2
c 3
d 4
e 5
a+d*(b*(c+d)-e)//1+4*(2*(3+4)-5)
输出
37

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define N 100
struct st{char name;int value;
};
int find(st s[],char x)
{//变量名查询变量值for(int i=0;i<5;i++){if(x==s[i].name)return s[i].value;}
}
int level(char x)
{//查询运算符优先级if(x=='('||x==')')return 1;else if(x=='+'||x=='-')return 2;else if(x=='*'||x=='/')return 3;return 1;
}
int clu(int x,int y,char ch)
{//x与y进行
//x (ch) y运算
//返回 x(ch)yint sum=0;switch(ch){case '+':sum=x+y;break;case '-':sum=x-y;break;case '*':sum=x*y;break;case '/':sum=x/y;break;			}return sum;
}
/*
a 1
b 2
c 3
d 4
e 5
*/
int main()
{st s[N];//变量数组(储存变量名和变量值)int sum=0;int k=0;int top=-1;//栈指针char str[N]="a+d*(b*(c+d)-e)";//1+4*(2*(3+4)-5)//中缀表达式char post[N];//后缀表达式数组char t,stack_[N];//运算符栈/*a=1b=2c=3d=4e=5*///printf("%d\n",1+4*(2*(3+4)-5));for(int i=0;i<5;i++){scanf("%c%d",&s[i].name,&s[i].value);getchar();}scanf("%s",str);//输入中缀表达式(数学表达式) for(int i=0;i<strlen(str);i++){//islower:判小写；isupper:判大写 if(islower(str[i])||isupper(str[i])){//变量名 ，单个字符(大小写都行) post[k++]=str[i];}else//运算符 {if(str[i]==')')//遇到右括号出栈 {while(stack_[top]!='('){//出栈的符号放入后缀表达式数组中 post[k++]=stack_[top];top--;}top--;}else if(top==-1||level(str[i])>level(stack_[top])||str[i]=='('){//栈空，当前运算符优先级大于栈顶运算符优先级，当前运算符为左括号//三种情况运算符直接入栈 stack_[++top]=str[i];}else if(level(str[i])<=level(stack_[top])){//前运算符优先级小于等于栈顶运算符优先级//栈顶元素出栈,直到 前运算符优先级大于栈顶运算符优先级while(level(str[i])<=level(stack_[top])&&top!=-1){//出栈元素加入后缀表达式数组中 post[k++]=stack_[top];top--;}//当前运算符入栈 stack_[++top]=str[i];}}}printf("\n");while(top!=-1)//栈内剩余运算符也加入后缀表达式数组 post[k++]=stack_[top--];top=-1;/*****输出后缀表达式******/for(int i=0;i<k;i++)printf("%c ",post[i]);printf("\n"); /***********************/ top=-1;int num[N]={0};//数字栈,用于后缀表达式求值 for(int i=0;i<k;i++){if(islower(post[i])||isupper(post[i])){//变量名 ，单个字符(大小写都行)//find(s,x)在s数组中根据变量名查找变量值//然后入栈 num[++top]=find(s,post[i]);}else//运算符 {int x=num[top];int y=num[top-1];//x,y栈顶两个元素//clu(y,x,post[i])//post[i]运算符//clu函数根据运算符求出x和y的运算结果 sum=clu(y,x,post[i]);top-=2;//x,y出栈 num[++top]=sum;//运算结果入栈 }}printf("\n%d",sum);return 0;
}