利用栈实现简单计算器
数据结构之利用栈实现简单计算器-C语言代码实现： juejin.cn/post/705011…
1. 中缀表达式 和 后缀表达式
中缀表达式: 顾名思义，操作符在操作数的中间，例如: 1 + 1
后缀表达式: 指操作符在操作后后面 ，例如 1 1 + ， 就代表 中缀表达式 的 1 + 1
关于具体的 请参考: baike.baidu.com/item/%E9%80…
2. 关于数据结构: 栈
栈就是一个先进先出的队列
C语言函数之间调用，就是使用栈进行的
参考: baike.baidu.com/item/%E6%A0…
3. 中缀表达式 如何利用栈 转换为后缀表达式
利用栈转换规则如下
遍历中缀表达式
- 判断为 数字 直接输出
- 判断为 ( 入栈
- 判断为 ) 则，出栈 直至遇到 (
- 判断为 * 或 /
- 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 <stdio.h> 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/*+ #
4. 利用栈 后缀表达式计算结果
利用栈计算后缀表达式规则如下
假设后缀表达式是有效的
遍历后缀表达式
- 判断为数字，则进行压栈
- 判断为操作符(+ - * /)
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 <stdio.h> 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 #
完
