表达式求值(栈)

题目描述

给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。

注意:

  • 数据保证给定的表达式合法。
  • 题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-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 }

 

上一篇:csp-二十四点


下一篇:更准确的测试Java程序性能——JMH基准测试