来源： https://www.cnblogs.com/NoneID/p/15777625.html
整理：李肖遥
中缀表达式: 顾名思义，操作符在操作数的中间，例如: 1 + 1
后缀表达式: 指操作符在操作后后面 ，例如 1 1 + ， 就代表 中缀表达式 的 1 + 1
关于具体的 请参考: https://baike.baidu.com/item/逆波兰式/128437
栈就是一个先进先出的队列
C语言函数之间调用，就是使用栈进行的
参考: https://baike.baidu.com/item/栈/12808149?fr=aladdin
利用栈转换规则如下
遍历中缀表达式
判断为 数字 直接输出
判断为 ( 入栈
判断为 ) 则，出栈 直至遇到 (
判断为 * 或 /
4.1 判断栈顶元素是否是 * 或 / ， 如果是 则出栈
4.2 若1不符合规则，再将这个字符入栈
5.1 判断栈顶元素是否是 * 或 / ，如果是，则全部出栈，然后再入栈
5.2 若1不符合，再将这个字符入栈
判断为 + 或 - ，则
若表达式计算完毕，将出栈所有数据
实际例子
通过栈，将式子 3+2(9+8)/3(3/5) 转换为后缀表达式
开始式子: 3+2*(9+8)/3*(3/5)
开始处理: 3
执行规则1，是数字直接输出
输出: 3
栈:
开始处理: +
执行规则 5.2 直接入栈
输出: 3
栈: +
开始处理: 2
执行规则1，是数字直接输出
输出: 32
栈: +
开始处理: *
执行规则4.2，直接入栈
输出: 32
栈: +*
开始处理: (
执行规则2，直接入栈
输出: 32
栈: +*(
开始处理: 9
执行规则1，直接入栈
输出: 329
栈: +*(
开始处理: +
执行规则5.2，直接入栈
输出: 329
栈: +*(+
开始处理: 8
执行规则1，直接入栈
输出: 3298
栈: +*(+
开始处理: )
执行规则3，出栈直至遇到 (
输出: 3298+
栈: +*
开始处理: /
执行规则4.1，将栈顶元素为*或/直接出栈，然后在入栈该操作符
输出: 3298+*
栈: +/
开始处理: 3
执行规则1,直接入栈
输出: 3298+*3
栈: +/
开始处理: *
执行规则4.1，将栈顶元素为*或/直接出栈，然后在入栈该操作符
输出: 3298+*3/
栈: +*
开始处理: (
执行规则2,直接入栈
输出: 3298+*3/
栈: +*(
开始处理: 3
执行规则1,直接入栈
输出: 3298+*3/3
栈: +*(
开始处理: /
执行规则4.2,入栈
输出: 3298+*3/3
栈: +*(/
开始处理: 5
执行规则1,直接入栈
输出: 3298+*3/35
栈: +*(/
开始处理: )
执行规则3,出栈 直至遇到(
输出: 3298+*3/35/
栈: +*
开始处理: )
执行规则6,全部出栈
输出: 3298+*3/35/*+
栈:
得到中缀表达式: 3298+*3/35/*+
完毕
转换代码 C语言实现:
# include
int main() {
// 中缀表达式
char formula[] = "3+2*(9+8)/3*(3/5)";
// 栈
char options[sizeof(formula) * sizeof(char)];
int stackLen = -1;
printf("%s\n",formula);
int i;
for (i = 0; formula[i]!='\0'; i++) {
// 规则1
if (formula[i] >= '0' && formula[i] <= '9') {
printf("%c",formula[i]);
}
switch (formula[i]) {
// 规则2
case '(': {
stackLen += 1;
options[stackLen] =formula[i];
break;
}
// 规则3
case ')': {
while (stackLen >= 0 && (options[stackLen] != '(')) {
printf("%c",options[stackLen]);
stackLen -= 1;
}
stackLen-=1;
break;
}
// 规则4
case '*':
case '/': {
while (stackLen >= 0 && (options[stackLen] == '*' || options[stackLen] == '/')) {
printf("%c",options[stackLen]);
stackLen -= 1;
}
stackLen += 1;
options[stackLen] = formula[i];
break;
}
// 规则5
case '+':
case '-': {
if (stackLen >= 0 && (options[stackLen] == '*' || options[stackLen] == '/')) {
while (stackLen >= 0) {
printf("%c",options[stackLen]);
stackLen -= 1;
}
}
stackLen += 1;
options[stackLen] = formula[i];
break;
}
}
}
// 规则6
while (stackLen >= 0) {
printf("%c",options[stackLen]);
stackLen--;
}
printf("\n");
}
执行结果
# gcc calTest1.c
# ./a.out
3+2*(9+8)/3*(3/5)
3298+*3/35/*+
#
利用栈计算后缀表达式规则如下
假设后缀表达式是有效的
遍历后缀表达式
判断为数字，则进行压栈
判断为操作符(+ - * /)
2.1 出栈2个元素，m 和 n (对于当前栈而言,m: 栈顶元素 n: 栈顶第二个元素)
2.2 计算 n 操作符 m ,然后将结果 入栈
实际例子
通过栈，将计算后缀表达式 3298+*3/35/*+ 的值
式子: 3298+*3/35/*+
开始处理: 3
执行规则1: 直接入栈
栈: 3
开始处理: 2
执行规则1: 直接入栈
栈: 3 2
开始处理: 9
执行规则1: 直接入栈
栈: 3 2 9
开始处理: 8
执行规则1: 直接入栈
栈: 3 2 9 8
开始处理: +
执行规则2: 取出2个元素, m:8 n:9 , 并且执行结果（n + m）入栈
栈: 3 2 17
开始处理: *
执行规则2: 取出2个元素, m:17 n:2 , 并且执行结果(n * m)入栈
栈: 3 34
开始处理: 3
执行规则1: 直接入栈
栈: 3 34 3
开始处理: /
执行规则2: 取出2个元素, m:3 n:34 , 并且执行结果(n / m)入栈
栈: 3 11.3
开始处理: 3
执行规则1: 直接入栈
栈: 3 11.3 3
开始处理: 5
执行规则1: 直接入栈
栈: 3 11.3 3 5
开始处理: /
执行规则2: 取出2个元素, m:5 n:3 , 并且执行结果(n / m)入栈
栈: 3 11.3 0.6
开始处理: *
执行规则2: 取出2个元素, m:0.6 n:11.3 , 并且执行结果(n * m)入栈
栈: 3 6.8
开始处理: +
执行规则2: 取出2个元素, m:6.8 n:3 , 并且执行结果(n + m)入栈
栈: 9.8
计算结果: 9.8
完成
用C实现该代码
转换代码 C语言实现:
# include
int main() {
// 后缀表达式
char formula[] = "3298+*3/35/*+";
// 栈
float options[sizeof(formula) * sizeof(char)];
int stackLen = -1;
printf("%s\n",formula);
int i;
for(i=0;formula[i]!='\0';i++) {
// 规则1
if (formula[i] >= '0' && formula[i] <= '9') {
stackLen++;
options[stackLen] = (float)(formula[i]-48);
} else {
// 规则2
float m = options[stackLen];
stackLen--;
float n = options[stackLen];
stackLen--;
switch (formula[i]) {
case '*': {
stackLen++;
options[stackLen] = (n * m);
break;
}
case '/': {
stackLen++;
options[stackLen] = (n / m);
break;
}
case '+': {
stackLen++;
options[stackLen] = (n + m);
break;
}
case '-': {
stackLen++;
options[stackLen] = (n - m);
break;
}
}
}
}
printf("\n结果为: %.2f\n" , options[0]);
}
执行结果
# ./a.out
3298+*3/35/*+
结果为: 9.80
#‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ END ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧
关注我的微信公众号，回复“加群”按规则加入技术交流群。
点击“阅读原文”查看更多分享，欢迎点分享、收藏、点赞、在看。
