【数据结构】表达式求值

【题目链接】

　　https://www.acwing.com/problem/content/description/153/

【题目描述】

　　给出一个表达式,其中运算符仅包含+,-,*,/,^（加减乘整除乘方）要求求出表达式的最终值。

　　数据可能会出现括号情况，还有可能出现多余括号情况。

　　数据保证不会出现大于或等于 $2^{31}$

　　数据可能会出现负数情况。

输入格式

　　输入仅一行，即为表达式。

输出格式

　　输出仅一行，既为表达式算出的结果。

输入样例：

　　(2+2)^(1+1)

输出样例：

【题解】：

1、处理括号问题，由于又多余的括号，我们发现左括号是没有用的，所以我们匹配尽量多的左括号，然后配上一个右括号即可。

2、维护两个栈的操作。

　　第一个栈是维护操作数，如果运算的时候就弹出两个出来，然后运算结果又放回去，最后求数字栈的栈顶元素即可。

　　第二个栈是维护一个严格递增的操作符，操作符是优先级的。“+” = “-” < “*” = “/” < “^”，严格递增。每次压栈时都加优先级比较，如果不是严格递增的就弹出来运算一遍然后压回去。注意注意！！！存在负数的时候是而又不是正数。

【代码】代码是仿造y总的写法，不得不说，y总码力十足。

 1 #include<string>
 2 #include<stack>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 stack < int > Nums ;
 7 stack < char > ops ; 
 8 void Calc(){
 9     int tmp = 1 ;
10     int v = Nums.top() ; Nums.pop();
11     int u = Nums.top() ; Nums.pop(); 
12     char ch = ops.top() ; ops.pop() ;
13     if( ch == '+' ) tmp = u + v; 
14     else if( ch == '-' ) tmp = u - v ;
15     else if( ch == '*' ) tmp = u * v ;
16     else if( ch == '/' ) tmp = u / v ;
17     else if( ch == '^' ){
18         while ( v -- ) tmp = tmp * u ;
19     }
20     Nums.push( tmp ) ;
21 }
22 
23 int main()
24 {
25     ios_base :: sync_with_stdio(false);
26     cin.tie(NULL) , cout.tie(NULL) ;  
27     string str , Left = ""; 
28     cin >> str;
29     int n = str.length() ;
30     for(int i=0 ; i<=n ; i++ ) Left = Left + "(" ;
31     
32     str = Left + str + ")"; 
33     n = str.length() ; 
34     
35     //cout << str << endl;
36     for(int i=0 ; i < n ; i++ ){
37         if( '0' <= str[i] && str[i] <= '9' ){
38             int tmp = 0 ;
39             int j = i ;
40             while( '0' <= str[j] && str[j] <= '9' ){
41                 tmp = tmp * 10 + str[j] - '0' ;
42                 j ++ ;
43             }
44             Nums.push(tmp);
45             i = j - 1 ;
46         }else{
47             char c = str[i] ; 
48             if( c == '(' ){
49                 ops.push(c);
50             }else if( c == '+' || c == '-' ){
51                 
52                 if( c == '-' && i && !('0' <= str[i-1] && str[i-1] <= '9' || str[i-1] == ')' ) ){
53                     int tmp = 0 ;
54                     int j = i+1 ;
55                     while( '0' <= str[j] && str[j] <= '9' ){
56                         tmp = tmp * 10 + str[j] - '0' ;
57                         j ++ ;
58                     }
59                     Nums.push(-tmp);
60                     i = j - 1 ;
61                 }else{
62                     while( ops.top() != '(' ) Calc();
63                     ops.push( c );
64                 }
65             }else if( c == '*' || c == '/' ){
66                 //维护单调递增的栈 * / 
67                 while ( ops.top() == '*' || ops.top() == '/' || ops.top() == '^' ) Calc();
68                 ops.push(c);
69             }else if( c == '^' ){
70                 while ( ops.top() == '^' ) Calc() ;
71                 ops.push(c);
72             }else if( c == ')' ){
73                 while ( ops.top() != '(' ) Calc();
74                 ops.pop();
75             }else puts(" Invaild Operator !" );
76         }
77     }
78     cout << Nums.top() << endl;
79     return 0;
80 }

View Code