大家好，又见面了，我是你们的朋友全栈君。

相关链接：

1. 表达式求值汇总
2. 多位数表达求值

表达式

表达式求值

【步骤】表达式–>后缀表达式–>求值

1. 表达式转后缀表达式：

2. 后缀表达式求值：

   

表达式转后缀表达式

步骤

Stack OPND; //存储后缀【表达式】的栈
Stack OPTR; //存储【符号】的栈
OPTR.push('#') //将一个#压在最下面，做标识，为了更好统一比较

扫描原表达式，得到c
	if c==数字:
		放入OPND
	if c==符号：
		c前面的一个符号top（OPTR的栈顶元素）
		//c与top进行优先级比较
		if c<top：
			OPTR.pop()
			OPTR.push(top) //将c放入符号栈
		else if c>top：
			OPTR.push(c)  //将c放到符号栈
		else if c==top:
			continue

运算符表

【说明】先运算则优先级大

• 【行c1】扫描到的运算符c1
• 【列c2】在C1之前的运算符c2

【例子】

• 【例1】1+2+3

  • 扫描到c1=+（第二个+），c1前面的符号也是+（即c2=+，第一个+）
  • 应该先运算1+2，即c2应该先运算（第一个+），所以c1<c2

• 【例2】1+(1…

  • 扫描到c1=’(’，c1前面的一个符号是+，即c2=+
  • 应该先运算括号里的，即c1先运算，所以c1’>’c2

• 【例3】(1+1…

  • 扫描到c1=+，c1前面的一个符号是(，即c2=(
  • 应该运算1+1，等同于c1运算，(后运算，所以c1’>’c2

• 【例4】…1)+2

  • 扫描到c1=+，c1前面的一个符号是)
  • 括号里的先运算，即)先运算，所以c1’<‘c2

【总结】抓住一个原则：c1前面的c2，如果c2先运算，即c1<c2
例如：+(c1)前面是+(c2)，后面的+先与运算，即+<+

例子

【代码】支持2位以上的数字

【代码说明】支持：2位以上的数字，四则运算和幂运算
使用的栈，是自己实现，封装在2 SqStack.h文件中的，可自己实现，也可以参照：https://blog.csdn.net/summer_dew/article/details/82051767
【结果】
测试：10*(1*(2+6/3)-1)+3^(3-1)+1+1-2# 结果为

// 顺序栈
// 顺序栈
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define SElemType int
#include"2 SqStack.h"
void visit(SElemType e) { 

printf("%d ",e);
}
void visit_optr(SElemType e) { 

printf("%c ",e);
}
void Show(SqStack *pOPTR, SqStack *pOPND,char c) { 

//printf("| 步骤 | 操作数栈OPND | 操作符栈OPTR | 输入字符 |\n");
static int first = 1;
if (first==1) { 

printf("当前扫描的字符\t数字栈\t符号栈\n");
first++;
}
printf("%c\t",c);
StackTraverse(*pOPND, &visit);printf(" \t");
StackTraverse(*pOPTR, &visit_optr);
printf("\n");
}
//将操作符转换成矩阵下标
int getIndex(char c) { 
 
switch(c) { 

case '+': return 0;
case '-': return 1;
case '*': return 2;
case '/': return 3;
case '(': return 4;
case ')': return 5;
case '^': return 6;
case '#': return 7;
}
return -1;
}
// 两个操作数比较
// c1>c2 TRUE
// c1<c2 FALSE
int compare_op(char c1,char c2) { 

char result;
static char priorityMatrix[8][8] = 
{ 
  // + - * / ( ) ^ #
{ 
'<','<','<','<','>','<','<','>'}, //+
{ 
'<','<','<','<','>','<','<','>'}, //-
{ 
'>','>','<','<','>','<','<','>'}, //*
{ 
'>','>','<','<','>','<','<','>'}, ///
{ 
'>','>','>','>','>','>','>','>'}, //(
{ 
'<','<','<','<','=','<','<','>'}, //)
{ 
'>','>','>','>','>','<','>','>'}, //^
{ 
'<','<','<','<','<','<','<','='}  //#
};
// 转换下标
int c1_index = getIndex(c1);
int c2_index = getIndex(c2);
// 矩阵
result =  priorityMatrix[c1_index][c2_index];
switch (result) { 

case '<' : return -1; // c1<c2
case '>' : return 1; // c1>c2
case '=' : return 0; // c1=c2错误情况
}
return 0;
}
int Operate(int S1,char OP,int S2) { 

switch (OP) { 

case '+':
return S1+S2;
case '-':
return S1-S2;
case '*':
return S1*S2;
case '/':
return S1/S2;
case '^':
return (int)pow(S1,S2);
}
return 0;
}
//表达式求值：规定为整数，未检查异常
/* 测试数据:
10+11+12#
10*(1*(2+6/3)-1)+3^(3-1)+1+1-2#
*/
int main() { 

SqStack OPTR; //存放符号（操作符）
SqStack OPND; //存放数值（操作数）
char c; //每次获得的字符
int num,S1,S2,result,tmp,OP; //存放数字
//初始化
InitStack(&OPTR);
Push(&OPTR, '#');
InitStack(&OPND);
printf("请输入表达式：\n");
c=getchar();
num=0;
while ( !StackEmpty(OPTR) ) { 

if (c>='0' && c<='9') { 
 //数字
num = num*10 + c-'0'; //保存数字
Show(&OPTR, &OPND, c); //UI
printf("\t\t\t\t【操作】是数字%d\n",num); //UI
} else { 
 //操作符
if (num!=0) { 
 //之前有数字
Push(&OPND, num); //入栈
printf("\t\t\t\t【操作】至此，前面的扫描中得到一个数字%d，入栈\n",num); //UI
Show(&OPTR, &OPND, c); //UI
num =0; //归为0
}
GetTop(OPTR, &OP); //取出操作符栈顶元素
//与上一个符号比较优先级
tmp = compare_op((char)c, (char)OP);
printf("\t\t\t\t【操作】优先级比较：%c与%c\n",c,OP);
if ( tmp==1 ) { 
 //c>tmp
Push(&OPTR, c); //压栈
Show(&OPTR, &OPND, c); //UI
printf("\t\t\t\t【操作】将符号%c压栈\n",c); //UI
} else if ( tmp==-1 ){ 
 //c<tmp
Pop(&OPTR, &OP);
Pop(&OPND, &S2); //先取出的是后面一位的数字 
Pop(&OPND, &S1);
result = Operate(S1, (char)OP, S2);
Push(&OPND, result);
Show(&OPTR, &OPND, c); //UI
printf("\t\t\t\t【操作】进行计算%d%c%d=%d，将结果压栈\n",S1,OP,S2,result);//UI
continue; //不执行c=getchar()，当前的c还没有处理完
} else if (tmp==0){ 

// 1. c=) OP=(
// 2. c=# OP=#
Pop(&OPTR,&tmp); //将栈顶删除
Show(&OPTR, &OPND, c); //UI
printf("\t\t\t\t【操作】当前操作符和栈顶操作符相同，删除栈顶操作符\n");
}
}
c = getchar();
}
GetTop(OPND,&result);
printf("\n计算结果：%d\n", result);
return 0;
}