表达式求值（最详细分析+代码实现+表达式之间的相互转换）
目录
一、概念
算术表达式是由操作数（运算数）、运算符（操作符）、和界线符（括号）三部分组成，在计算机中进行算术表达式的计算是通过堆栈来实现的。
二、前缀表达式的逻辑和实现方式
1.定义
如果是在两个操作数之前，那么这个表达式就是前缀表达式，又称波兰表达式，如：-*+3 5 7 1
2.前缀表达式的计算机求值
1.从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，
2.弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），
3.并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
3.例子
计算前缀表达式的值：- + 1 × + 2 3 4 5
1)从右至左扫描，将5，4，3，2压入堆栈；
2）遇到+运算符，弹出2和3（2为栈顶元素，3为次顶元素），计算2+3的值，得到5，将5压入栈；
3）遇到×运算符，弹出5和4，计算5×4的值，得到20，将20压入栈；
4）遇到1，将1压入栈；
5）遇到+运算符，弹出1和20，计算1+20的值，得到21，将21压入栈；
6）遇到-运算符，弹出21和5，计算5-21的值，得到-16为最终结果
可以看到，用计算机计算前缀表达式是非常容易的，不像计算后缀表达式需要使用正则匹配
4.代码实现
三、中缀表达式的逻辑和实现方式
1.定义
如果是跟在两个操作数之间，那么这个表达式就是中缀表达式,如：(3 + 5) * 7 - 1
2.中缀表达式规则
(1) 先计算括号内，后计算括号外；
(2) 在无括号或同层括号内，先乘除运算，后加减运算，即乘除运算的优先级高于加减运算的优先级；
(3) 同一优先级运算，从左向右依次进行。
3.中缀表达式的计算机求值
- 设置两个栈，一个数字栈numStack，用于存储表达式中涉及到的数字，operatorStack用于存储表达式中涉及到的运算符
- 逐个字符分析表达式，直到全部字符都已分析完
- 若当前字符为数字，则判断是否后续字符也为数字，若为数字则进行拼接，直到下一个数字为运算符为止，此时将拼接好的多位数字压入数字栈中。（如果已经是最后一个字符则直接压入栈）
- 若当前字符为算数运算符
- 如果运算符栈为空则直接压入栈中
- 运算符不为空，则对运算符优先级进行判断
- 如果当前运算符优先级大于等于栈顶运算符则直接压入栈中
- 如果优先级低于栈顶运算符，则，从数字栈中取出两个数据，将当前栈顶运算符弹出进行运算，将结果压入数字栈中，将当前运算符压入运算符栈中。
- 此时数字与运算符都已经压入栈中，此时运算符栈中均为优先级相同的运算符，需要进行收尾操作，如果运算符栈不为空，则依次从数字栈中弹出两个数据，与当前栈顶的运算符进行运算。将结果压入数字栈中。最后数字栈中的数字就是所要求解的结果
4.代码实现
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#include <math.h>
#define maximum 100000
typedef struct//数字栈
{
float data[maximum];
int top;
}number;
typedef struct//字符栈
{
char data[maximum];
int top;
}sign;
void InitNumber(number *stack);//初始化数字栈
void GetTopNumber(number stack, float *e);//获取栈顶元素
void PushNumber(number *stack, float e);//进栈
void PopNumber(number *stack, float *e);//出栈
void InitSign(sign *stack);
void GetTopSign(sign stack, char *e);
void PushSign(sign *stack, char e);
void PopSign(sign *stack, char *e);
void Calculate(number *stack, char e);
number Num;
sign sig;
char expression[maximum];
int main()
{
gets(expression);
int length;
length=strlen(expression);
int i;
float en,n;
char es;
InitNumber(&Num);
InitSign(&sig);
for (i=0;i<length;i++)
{
if(expression[i]>='0'&&expression[i]<='9')
{
n=expression[i]-'0';//字符型转换为整型
while (expression[i+1]!='\0')
{
if (expression[i+1]>='0'&&expression[i+1]<='9')
{
n=n*10+expression[i+1]-'0';
++i;
}
else break;
}
PushNumber(&Num,n);
}
else if (expression[i]=='+'||expression[i]=='-'||expression[i]=='*'||expression[i]=='/'||expression[i]=='^'||expression[i]=='('||expression[i]==')')
{
switch (expression[i])
{
case '+':
if(sig.data[sig.top-1]!='+'&&sig.data[sig.top-1]!='-'&&sig.data[sig.top-1]!='*'&&sig.data[sig.top-1]!='/'&&sig.data[sig.top-1]!='^')
//与栈顶元素的优先级相比较， 高于时入栈，此处判断是否入栈。
PushSign(&sig,'+');
else
{
while (sig.top>0&&sig.data[sig.top-1]!='(')//如果栈不为空切不为左括号，则出栈
{
PopSign(&sig,&es);
Calculate(&Num,es);
}
PushSign(&sig,'+');
}
break;
case '-':
if(sig.data[sig.top-1]!='+'&&sig.data[sig.top-1]!='-'&&sig.data[sig.top-1]!='*'&&sig.data[sig.top-1]!='/'&&sig.data[sig.top-1]!='^')
PushSign(&sig,'-');
else
{
while (sig.top>0&&sig.data[sig.top-1]!='(')
{
PopSign(&sig,&es);
Calculate(&Num,es);
}
PushSign(&sig,'-');
}
break;
case '*':
if(sig.data[sig.top-1]!='*'&&sig.data[sig.top-1]!='/'&&sig.data[sig.top-1]!='^')
PushSign(&sig,'*');
else
{
while (sig.top>0&&sig.data[sig.top-1]!='(')
{
PopSign(&sig,&es);
Calculate(&Num,es);
}
PushSign(&sig,'*');
}
break;
case '/':
if(sig.data[sig.top-1]!='*'&&sig.data[sig.top-1]!='/'&&sig.data[sig.top-1]!='^')
PushSign(&sig,'/');
else
{
while (sig.top>0&&sig.data[sig.top-1]!='(')
{
PopSign(&sig,&es);
Calculate(&Num,es);
}
PushSign(&sig,'/');
}
break;
case '^':
if(sig.data[sig.top-1]!='^')
PushSign(&sig,'^');
else
{
while (sig.top>0&&sig.data[sig.top-1]!='(')
{
PopSign(&sig,&es);
Calculate(&Num,es);
}
PushSign(&sig,'^');
}
case '(':
PushSign(&sig,'(');
break;
case ')':
while (sig.data[sig.top-1]!='(')
{
PopSign(&sig,&es);
Calculate(&Num,es);
}
PopSign(&sig,&es);
}
}
}
while (sig.top>0)
{
PopSign(&sig,&es);
Calculate(&Num,es);
}
GetTopNumber(Num,&en);
printf("%.0f\n",en);
return 0;
}
void InitNumber(number *stack)
{
stack->top=0;
}
void GetTopNumber(number stack, float *e)
{
if(stack.top==0) return;
else *e=stack.data[stack.top-1];
}
void PushNumber(number *stack, float e)
{
if(stack->top>=maximum) return;
else stack->data[stack->top++]=e;
}
void PopNumber(number *stack, float *e)
{
if(stack->top==0) return;
else *e=stack->data[--stack->top];
}
void InitSign(sign *stack)
{
stack->top=0;
}
void GetTopSign(sign stack, char *e)
{
if(stack.top==0) return;
else *e=stack.data[stack.top-1];
}
void PushSign(sign *stack, char e)
{
if(stack->top>=maximum) return;//栈满
else
{
stack->data[stack->top]=e;
stack->top++;
}
}
void PopSign(sign *stack, char *e)
{
if(stack->top==0) return;
else *e=stack->data[--stack->top];
}
void Calculate(number *stack, char e)// 计算结果
{
float num1,num2,result;
PopNumber(stack, &num2);
PopNumber(stack, &num1);
switch (e)
{
case '+':
result=num1+num2;
PushNumber(stack,result);
break;
case '-':
result=num1-num2;
PushNumber(stack,result);
break;
case '*':
result=num1*num2;
PushNumber(stack,result);
break;
case '/':
if (num2==0) printf("表达式错误！");
else
{
result=num1/num2;
PushNumber(stack,result);
break;
}
case '^':
result=pow(num1,num2);
PushNumber(stack,result);
break;
}
}
四、后缀表达式的逻辑和实现方式（逆波兰表达式求值）
1.定义
如果每个操作符跟在它的两个操作数之后，而不是两个操作数之间，那么这个表达式就是后缀表达，又称为逆波兰表达式，如：3 5 + 7 * 1 -
2.后缀表达式计算机求值
1.与前缀表达式类似，只是顺序是从左至右：
2.从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，其中先出栈的是右操作数，后出栈的是左操作数，
3.用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；
4.重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
3.例子
计算后缀表达式的值：1 2 3 + 4 × + 5 -
1）从左至右扫描，将1，2，3压入栈；
2）遇到+运算符，3和2弹出，计算2+3的值，得到5，将5压入栈；
3）遇到4，将4压入栈
4）遇到×运算符，弹出4和5，计算5×4的值，得到20，将20压入栈；
5）遇到+运算符，弹出20和1，计算1+20的值，得到21，将21压入栈；
6）遇到5，将5压入栈；
7）遇到-运算符，弹出5和21，计算21-5的值，得到16为最终结果
4.代码实现
bool isNumber(char* token) {
return strlen(token) > 1 || ('0' <= token[0] && token[0] <= '9');
}
int evalRPN(char** tokens, int tokensSize) {
int n = tokensSize;
int stk[n], top = 0;
for (int i = 0; i < n; i++) {
char* token = tokens[i];
if (isNumber(token)) {
stk[top++] = atoi(token);
} else {
int num2 = stk[--top];
int num1 = stk[--top];
switch (token[0]) {
case '+':
stk[top++] = num1 + num2;
break;
case '-':
stk[top++] = num1 - num2;
break;
case '*':
stk[top++] = num1 * num2;
break;
case '/':
stk[top++] = num1 / num2;
break;
}
}
}
return stk[top - 1];
}
atoi函数的用法在另一篇文章有体现，其作用就是将字符串转化为整数型。
五、相互转换
1.中缀表达式转化为前缀表达式
①算法描述
(1)首先构造一个运算符栈S1和一个储存中间结果的栈S2。
(2)从右至左扫描中缀表达式
(3)如果是操作数时，将其压入S2。
(4)如果是运算符，则与S1栈顶元素比较优先级：
a) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
b) 否则，若该运算符优先级比栈顶运算符的较高或相等，也将运算符压入S1；
c) 否则，将S1栈顶的运算符弹出并压入到S2中，再与S1中新的栈顶运算符相比较
(5)遇到括号时：
a) 如果是右括号“)”，则直接压入S1；
b) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号 丢弃；
(6)重复步骤(2)至(5)，直到表达式的最左边；
(7)若表达式扫描完，将S1中剩余的运算符依次出栈并压入S2；
(8)依次将S2中的元素出栈，结果即为对应的前缀表达式。
②例子
2.前缀表达式转化为中缀表达式
3.中缀表达式转化为后缀表达式
①算法描述
(1)首先构造一个运算符栈S1和一个储存中间结果的栈或线性表S2。
(2)从左至右扫描中缀表达式
(3)如果是操作数时，将其压入S2。
(4)如果是运算符，则与S1栈顶元素比较优先级：
a) 如果S1为空，或栈顶运算符为右括号“(”，则直接将此运算符入栈；
b) 否则，若该运算符优先级比栈顶运算符的较高或相等，也将运算符压入S1；
c) 否则，将S1栈顶的运算符弹出并压入到S2中，再与S1中新的栈顶运算符相比较
(5)遇到括号时：
a) 如果是左括号“(”，则直接压入S1；
b) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
(6)重复步骤(2)至(5)，直到表达式的最右边；
(7)若表达式扫描完，将S1中剩余的运算符依次出栈并压入S2；
(8)从左往右依次读取S2中的元素，即为对应的后缀表达式。
②例子
③代码实现
//本程序只能处理有关运算符+、-、*、/的中缀表达式，不能是÷或者×及其他运算
//界限符只能是英文状态的左右括号即'('、')'，操作数只能是整数
//本程序不会检查输入的中缀表达式是否正确，因此请您核验好自己的式子是否正确
#include<stdio.h>
#include<string.h> //strlen的头文件，用于判断字符串长度
#include<stdlib.h> //malloc、free的头文件
#define size 50//假定要转换的中缀表达式的字符数在50个以内
typedef struct Linknode{ //定义链栈及结点
char data; //数据域
struct Linknode *next; //指针域
}*LiStack;
bool InitStack(LiStack &S){ //链栈的初始化，不带头结点
S=NULL; //刚开始没有结点
return true;
}
bool StackEmpty(LiStack S){ //判断栈空
return S==NULL;
}
bool Push(LiStack &S,char x){ //将元素x入栈
Linknode *s=(Linknode *)malloc(sizeof(Linknode)); //创建新结点
if(s==NULL) //内存不足，创建失败
return false;
s->data=x;
s->next=S; //将结点s作为链栈的栈顶结点
S=s; //栈顶指针S指向结点s
return true;
}
bool Pop(LiStack &S,char &x){ //栈顶元素出栈，将值赋给x
if(S==NULL)
return false; //栈空则返回NULL
x=S->data;
Linknode *p=S;
S=S->next;
free(p);
return true;
}
int main(){
char temp,a[size],b[size]; //静态数组a、b分别存放要转换的中缀表达式和转换后的后缀表达式,字符变量temp存放弹出的栈顶元素
scanf("%s",&a); //需要您输入中缀表达式
LiStack S;//初始化一个栈，用于保存括号和暂时还不能确定运算顺序的运算符
InitStack(S); //初始化链栈
int i,j,length=strlen(a); //length为输入的中缀表达式的总长度，i、j分别为静态数组a、b的索引下标
for(i=j=0;i<length;i++){
if(a[i]>=48 && a[i]<=57){ //若当前字符是数字,字符0-9的ACSII码范围是[48,57]
b[j++]=a[i];
if(a[i+1]=='+'||a[i+1]=='-'||a[i+1]=='*'||a[i+1]=='/') //若下一个字符是运算符，即+、-、*、/，则b加一个空格，以免不同的操作数混在一起
b[j++]=' ';
}
else if(a[i]=='(')
Push(S,a[i]); //若当前字符是左括号则直接入栈
else if(a[i]==')'){ //若当前字符是右括号
while(StackEmpty(S)==0){ //栈非空则不断弹出栈内字符并加入后缀表达式
Pop(S,temp);
if(temp=='(') //直到弹出左括号停止，注意这个(不加入后缀表达式
break;
b[j++]=temp;
b[j++]=' '; //加一个空格，从而将字符隔开
}
}
else switch(a[i]){ //若当前字符是运算符
case '*': case '/':{
while(StackEmpty(S)==0){ //若栈非空，则弹出栈中优先级高于或等于当前运算符的所有运算符，并将这些运算符加入后缀表达式
Pop(S,temp);
if(temp=='/'||temp=='*'){
b[j++]=temp;
b[j++]=' '; //加一个空格，从而将字符隔开
}
else if(temp=='('||temp=='-'||temp=='+'){//若栈顶元素是左括号或者是优先级低于当前字符的运算符，则将栈顶元素入栈
Push(S,temp);
break;
}
}
Push(S,a[i]); //把当前字符入栈
break;
}
case '-': case '+':{
while(StackEmpty(S)==0){ //若栈非空，则弹出栈中优先级高于或等于当前运算符的所有运算符，并将这些运算符加入后缀表达式
Pop(S,temp);
if(temp=='('){//若栈顶元素是左括号，则将栈顶元素入栈
Push(S,temp);
break;
}
else if(temp=='/'||temp=='*'||temp=='-'||temp=='+'){
b[j++]=temp;
b[j++]=' '; //加一个空格，从而将字符隔开
}
}
Push(S,a[i]); //把当前字符入栈
break;
}
}
}
while(StackEmpty(S)==0){ //栈非空时依次弹出栈顶元素并加入后缀表达式
Pop(S,temp);
b[j++]=temp;
b[j++]=' '; //加一个空格，从而将字符隔开
}
printf("结果是：\n");
for(i=0;i<j;i++) //j是数组中下一个可以插入元素的位置下标，因此b中存放字符的索引区间为[0,j-1]
printf("%c",b[i]); //输出b中的元素
printf("\n");
return 0;
}
4.后缀表达式转化为中缀表达式
同上前缀表达式转中缀表达式的原理一致，区别在于前缀是从右往左扫描，后缀表达式是从左往右扫描。
六、总结
1.常用表达式求值分析
①方法
常见的方法有两种，一种是中缀表达式求值，一种是后缀表达式求值
②优缺点
中缀表达式：符合人的习惯，但是在计算机中计算时要考虑其优先级和括号的关系，实现起来比较麻烦
后缀表达式：在计算机中实现时不需要考虑优先级和括号，因为后缀表达式已经将其解决了，但是不符合人的习惯
2.相互转换分析
①关于前缀的转换是从右向左扫描的
②关于后缀的转换是从左向右转换的
3.总结
不管是怎么样转换和怎么样计算，思路理解起来都没那么难，难就难在代码的实现上，虽然我赋有代码，但是这些代码是我从别的博客上整理来的，由于太多了不记得那是哪了，要是涉及侵权之类的请联系我，我立马删除。
代码有了、思路也有了，关键就是代码的实现上了，这个一定要自己敲，就算是照着敲一遍也比复制粘贴的好，边敲边理解，到最后看能不能用自己的思路敲出来。
作为码农，代码还是要多敲的，之前忽略了，现在就要恶补了，目前每天刷两道Leetcode来弥补。
代码的实践还是很重要的！
代码的实践还是很重要的！
代码的实践还是很重要的！
花了一天的时间整理出来的，希望对个位有帮助，有什么不理解的也可以留言，或者加我QQ：2417734199。
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
82
0- 0
已为社区贡献3条内容
所有评论(0)