-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStack_Expression_evaluation.cpp
More file actions
94 lines (87 loc) · 1.78 KB
/
Copy pathStack_Expression_evaluation.cpp
File metadata and controls
94 lines (87 loc) · 1.78 KB
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
#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <stack>
#include <cctype>
using namespace std;
// map's initial is different from python.
unordered_map<char, int> pr = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
stack<int> num;
stack<char> op;
string s;
void eval()
{
// two num pop and one operator pop
// result push into stack
int a = num.top();
num.pop();
int b = num.top();
num.pop();
char tempOp = op.top();
op.pop();
int r = 0;
if (tempOp == '+')
{
r = b + a;
}
else if (tempOp == '-')
{
r = b - a;
}
else if (tempOp == '*')
{
r = b * a;
}
else
{
r = b / a;
}
num.push(r);
}
int main()
{
// 这里的s是表达式
cin >> s;
// for循环用来将数字和操作符变成两个栈中的元素
for (int i = 0; i < s.size(); i++)
{
if (isdigit(s[i]))
{
int x = 0, j = i;
while (j < s.size() && isdigit(s[j]))
{
x = x * 10 + s[j] - '0';
j++;
}
// important
i = j - 1;
// x计算完一定要记得放入到num里
num.push(x);
}
else if (s[i] == '(')
{
op.push(s[i]);
}
else if (s[i] == ')')
{
while (op.top() != '(')
eval();
op.pop();
}
else
{
// important
while (op.size() && pr[s[i]] <= pr[op.top()])
{
// 先把栈中的高优先级符号的运算先计算了
eval();
}
op.push(s[i]);
}
}
while (op.size())
eval();
cout << num.top() << endl;
return 0;
}