stack实现简单计算器
徐仓仓 Lv3
  2022-07-09 13:54:44 2022-07-09 13:54    

stack实现简单计算器

思路

  1. 通过一个 index 值（索引），遍历表达式

  2. 如果发现是一个数字, 就直接入数栈。

  3. 如果发现扫描到是一个符号, 就分如下情况：

    1. 如果当前的符号栈为空，就直接入栈。

    2. 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈。

      再与新的符号栈顶进行比较，直到不再小于或等于栈顶操作符，将当前的操作符入符号栈。

    3. 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈。

  4. 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行。

  5. 最后在数栈只有一个数字，就是表达式的结果。

代码

Codeup简易计算器

代码写了很久，因为网上的教程在3.2步时：比较新操作符与栈顶的优先级，若小于或等于栈顶，则pop出两个数，pop出一个符号进行计算，随后将新符压入符号栈，并没有继续比较新的栈顶。对于公式1-2*3+4*5；当所有字符都被压入栈后，符号栈为-、*，数字栈为1、6、20，最后计算时：6*20=120，1-120=-119。

另外，弹出数字后，应注意是a-b，还是b-a。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//stack codeup 问题 A: 简单计算器
#include <iostream>
#include <stack>
#include <map>
#include <string>
using namespace std;
double cal(double a, double b, char t) {
	if (t == '+') {
		//cout << b + a << endl;
		return b + a;
	}
	else if (t == '-') {
		//cout << b - a << endl;
		return b - a;
	}
	else if (t == '/') {
		//cout << b / a << endl;
		return b / a;
	}
	else {
		//cout << b * a << endl;
		return b * a;
	}
}
int main() {
	//char s[200];
	string s;
	map<char, double> op;
	op['+'] = 0;
	op['-'] = 0;
	op['*'] = 1;//优先级更高
	op['/'] = 1;
	while (getline(cin, s)) {
		//cout << "size" << s.size() << endl;
		stack <char>oper;
		stack <double>num;
		if (s[0] == '0' && s.size() == 1)
			break;
		//cout << s;
		for (int i = 0; i < s.size();) {
			if (s[i] == ' ') {
				i++;
				continue;
			}
			if (!(s[i] >= '0' && s[i] <= '9')) {//符号
				if (oper.empty() == true) {//如果符号栈空，则直接入栈
					char n = s[i];
					oper.push(n);
					//cout << "符号入栈" << oper.top() << endl;
				}
				else {//符号栈非空，与top进行优先级比较
					if (op[s[i]] <= op[oper.top()]) {//出两个数字和一个操作符进行计算
						while (oper.size() >= 1 && op[s[i]] <= op[oper.top()]) {//继续比较
							double a = num.top();//数字出栈
							num.pop();
							//cout << "数字出栈" << a << " ";
							double b = num.top();
							num.pop();
							//cout << "数字出栈" << b << " ";
							char t;//符号出栈
							t = oper.top();
							oper.pop();
							//cout << "符号出栈" << t << " ";
							double ans = cal(a, b, t);
							num.push(ans);
						}
						oper.push(s[i]);
					}
					else {//新运算符优先级高，直接入栈
						oper.push(s[i]);
						//cout << "符号入栈" << oper.top();
					}
				}
				i++;
			}
			else {//数字
				int temp = s[i] - '0';
				i++;
				while (s[i] >= '0' && s[i] <= '9') {
					temp = temp * 10 + s[i] - '0';
					i++;
				}
				//cout << "数字入栈" << temp << endl;
				num.push(temp);
			}
		}
		//double ans = num.top();
		//cout << ans << endl;
		while (num.size() >= 2) {
			double a = num.top();
			num.pop();
			double b = num.top();
			num.pop();
			char t = oper.top();
			oper.pop();
			double ans = cal(a, b, t);
			num.push(ans);
		}
		printf("%.2f\n", num.top(), "\n");
	}
}

中缀转后缀

1+((2+3)* 4)-5 转换为123+4*+5–

思路

  1. 遍历中缀表达式。
  2. 当读到数字时，立即把它输出，即成为后缀表达式的一部分。
  3. 若读到操作符，判断该符号与栈顶符号的优先级：
    1. 若该符号优先级高于栈顶元素，则将该操作符入栈。
    2. 否则就一次把栈中运算符弹出并加到后缀表达式尾端，直到遇到优先级低于该操作符的栈元素，然后把该操作符压入栈中。
    3. 如果遇到”(”，直接压入栈中，如果遇到一个”)”，那么就将栈元素弹出并加到后缀表达式尾端，但左右括号并不输出。
  4. 最后，如果读到中缀表达式的尾端，将栈元素依次完全弹出并加到后缀表达式尾端。

中缀转前缀

1+((2+3)*4)–5转为\-+1*+2345

思路

  1. 从右至左遍历中缀表达式。
  2. 如果是数字，直接输出，作为前缀表达式的一个直接转换表达式Temp（最后，前缀表达式由该表达式翻转得到）；
  3. 如果是运算符，则比较优先级：
    1. 若该运算符优先级大于等于栈顶元素，则将该运算符入栈。
    2. 否则栈内元素出栈并加到Temp表达式尾端，直到该运算符大于等于栈顶元素的优先级时，再将该运算符压入栈中。
    3. 遇到右括号直接压入栈中，如果遇到一个左括号，那么就将栈元素弹出并加到Temp表达式尾端，但左右括号并不输出。
  4. 最后，若运算符栈中还有元素，则将元素一次弹出并加到Temp表达式尾端，最后一步是将Temp表达式翻转。

前缀转中缀

-+1*+2345转为5-(1+(2+3)*4)

思路

只有数字栈

  1. 从右到左扫描前缀表达式
  2. 如果遇到数字，则入栈。
  3. 如果遇到操作符，则将栈顶个元素弹出，并和操作符结合写成表达式，作为中缀表达式。
  4. 如果遇到的操作符优先级大于已存在表达式的最后执行操作符的优先级，则将已存在的表达式加上（）。

参考 前缀、中缀、后缀表达式转换详解

 Comments