【题目描述】
给定一个表达式,其中运算符仅包含 +,-,*,/
(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。
注意:
- 数据保证给定的表达式合法。
- 题目保证符号
-
只作为减号出现,不会作为负号出现,例如,-1+2
,(2+2)*(-(1+1)+2)
之类表达式均不会出现。 - 题目保证表达式中所有数字均为正整数。
- 题目保证表达式在中间计算过程以及结果中,均不超过 231−1。
- 题目中的整除是指向 0 取整,也就是说对于大于 0 的结果向下取整,例如 5/3=1,对于小于 0 的结果向上取整,例如 5/(1−4)=−1。
- C++和Java中的整除默认是向零取整;Python中的整除
//
默认向下取整,因此Python的eval()
函数中的整除也是向下取整,在本题中不能直接使用。
【输入格式】
共一行,为给定表达式。
【输出格式】
共一行,为表达式的结果。
【数据范围】
表达式的长度不超过 105。
【输入样例】
(2+2)*(1+1)
【输出样例】
8
对于一个中缀表达式,优先级高的应当被先算,低的则后算,那么体现在树上就是运算符优先级高的表达式树应当处于越下端。
思路:
①从左到右遍历表达式,遇到数字就把数字压入数字栈;
②遇到运算符,则比较当前运算符与栈顶运算符的优先级,如果当前运算符的优先级小于栈顶运算符,则说明栈内运算应当要被计算,弹出数字栈数据与栈顶运算符进行运算,将结果压入数字栈中;
③遇到左括号则直接入运算符栈;
④遇到右括号则不断弹出弹出数字栈数据与栈顶运算符进行运算,将结果压入数字栈中,直到下一个栈顶运算符为左括号,将其弹出并继续遍历表达式。
1 #include <iostream> 2 #include <stack> 3 #include <unordered_map> 4 #include <string> 5 using namespace std; 6 stack<int> num; 7 stack<char> op; 8 unordered_map<char,int> pri = {{'+',1},{'-',1},{'*',2},{'/',2}}; 9 10 void eval() 11 { 12 int b = num.top();num.pop(); 13 int a = num.top();num.pop(); 14 char ope = op.top();op.pop(); 15 if(ope == '+') num.push(a + b); 16 else if(ope == '-') num.push(a - b); 17 else if(ope == '*') num.push(a * b); 18 else num.push(a/b); 19 } 20 21 int main() 22 { 23 string str; 24 cin >> str; 25 for(int i = 0;i < str.size();++i) 26 { 27 char s = str[i]; 28 if(isdigit(s)) 29 { 30 int n = 0,j = i; 31 while(j < str.size() && isdigit(str[j])) 32 { 33 n = n*10 + str[j] - '0'; 34 ++j; 35 } 36 num.push(n); 37 i = j - 1; 38 } 39 else if(s == '(') op.push(s); 40 else if(s == ')') 41 { 42 while(op.top() != '(') 43 eval(); 44 op.pop(); 45 } 46 else 47 { 48 while(op.size() && pri[op.top()] >= pri[s]) 49 eval(); 50 op.push(s); 51 } 52 } 53 while(op.size()) 54 eval(); 55 cout << num.top() << endl; 56 return 0; 57 }