原理:给出中缀表达式,求出表达式的值。利用栈来模拟表达式树的操作。
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
| #include <iostream> #include <stack> #include <unordered_map> #include <string> using namespace std;
stack<int> nums; stack<char> op;
void eval() { auto b = nums.top(); nums.pop(); auto a = nums.top(); nums.pop(); auto c = op.top(); op.pop(); if(c == '+') nums.push(a + b); else if(c == '-') nums.push(a - b); else if(c == '*') nums.push(a * b); else if(c == '/') nums.push(a / b); }
int main(){ string str; unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; cin >> str; for(int i = 0; i < str.size(); i++) { auto c = str[i]; if(isdigit(c)) { int x = 0, j = i; while(isdigit(str[j])) x = x * 10 + str[j++] - '0'; i = j - 1; nums.push(x); } else if(c == '(') op.push(c); else if(c == ')') { while(op.top() != '(') eval(); op.pop(); } else { while(op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval(); op.push(c); } } while(op.size()) eval(); cout << nums.top(); }
|