[27. Expression evaluation (infix expression)]

Expression evaluation （ Infix ）

The premise to prepare
It needs to be opened up Two stacks , One for the Store numbers , Another one for Store operators .
Need to use unordered_map For storage Operator precedence .

step

（2 + 2 * 3）+ （4 * 5） Ordinary formula is infix expression

• Read each object of infix expression from beginning to end , Treat different objects according to different situations .

1.  Operands :  Direct output ;
2.  Left parenthesis :  Push into the stack ;
3.  Right bracket : Pop up the operator at the top of the stack and output , Until the left parenthesis ( Out of the stack , No output )
4.  Operator :
     If the priority is higher than the stack top operator , Then stack it up ;
     If the priority is less than or equal to the stack top operator , Pop up the stack top operator and output ; Again 
 Newer stack top operators , Until the operator is greater than the stack top operator priority , Then stack the operator ;
5  If all objects are processed , Then input the operators remaining in the stack !. 

The illustration

“ Expression evaluation ” problem , Two core key points ：

（1） Double stack , A stack of operands , An operator stack ;

（2） Operator priority , Top of stack operators , and , Priority comparison of operators to be put on the stack ：

If the operator at the top of the stack has low priority , The new operator is directly put on the stack

If the operator at the top of the stack has high priority , First out stack calculation , The new operator is pushed back onto the stack

Still with 1 + 2 + 3 * 4 * 5 give an example , See how to use the above two key points to implement the calculation .

First , The only example is + and * Two operators , So its operator table is ：

The meaning here is ：

（1） If the top of the stack is +, What's going to be on the stack is +, Stack top priority is high , need To calculate , Go back to the stack ;

（2） If the top of the stack is +, What's going to be on the stack is *, Stack top priority is low , Direct stack ;

（3） If the top of the stack is *, What's going to be on the stack is +, Stack top priority is high , need To calculate , Go back to the stack ;

（4） If the top of the stack is *, What's going to be on the stack is *, Stack top priority is high , need To calculate , Go back to the stack ;

In limine , Initialize the input string , And the operand stack , Operator stack .

Step by step, , Scan string , The operands are stacked one by one , Operators are also stacked .

When the next operator is to be stacked , You need to compare priorities first .

The priority in the stack is high , Must calculate first , To get into the stack .

The calculation process is ：

（1） Operand out of stack , As num2;

（2） Operand out of stack , As num1;

（3） Operator out of stack , As op;

（4） Calculate the result ;

（5） The result is put into the operand stack ;

Next , Operators and operands can continue to be stacked . When the next operator is to be stacked , Continue to compare the priority with the top of the stack .

The priority in the stack is low , You can put it directly on the stack .

The string continues to move .

It's time to compare priorities again .

The priority in the stack is high , Let's calculate first （3*4=12）, Go back to the stack .

Keep piling , Until the string is scanned .

Keep coming out of the stack , Until you get the final result 3+60=63, Algorithm complete .

subject

Given an expression , The operator only contains +,-,*,/（ Add reduce ride to be divisible by ）, May contain parentheses , Please find the final value of the expression .

Be careful ：

• The data guarantees that the given expression is legal .
• Title Guarantee symbol - Appears only as a minus sign , Will not appear as a minus sign , for example ,-1+2,(2+2)*(-(1+1)+2) Such expressions will not appear .
• Ensure that all numbers in the expression are positive integers .
• The title ensures that the expression is in the intermediate calculation process and the result , Not more than 2³¹−1.
• The division in the title points to 0 integer , That is, for greater than 0 The result is rounded down , for example 5/3=1, For less than 0 The result is rounded up , for example 5/(1−4)=−1
• C++ and Java The default division in is rounding to zero ;Python Integer division in // Round down by default , therefore Python Of eval() The integer division in the function is also rounded down , You can't use... Directly in this question .

Input format

All in one line , For the given expression .

Output format

All in one line , Is the result of the expression .

Data range

The length of the expression does not exceed 10₅.

sample input ：

(2+2)*(1+1)

sample output ：

8

Code

#include<iostream>
#include<unordered_map>
#include<stack>

using namespace std;


stack<int> num;      // Store operands  
stack<char> op;     // Storage operators 
                    // Establish a map to determine the operation priority 
unordered_map<char, int> cmp = {
    
    {
    '+', 1}, {
    '-', 1} , {
    '*', 2}, {
    '/', 2}
};
// Simulate an arithmetic operation 
void eval(void){
    
    int b = num.top();  num.pop();    // The second operand 
    int a = num.top();  num.pop();    // The first operand 
    char opr = op.top();    op.pop(); // Operator 

    int x;                             // result  
    // The result of the calculation is 
    if(opr == '+')  x = a + b;
    else if(opr == '-') x = a - b;
    else if(opr == '*') x= a * b;
    else    x = a / b;
    num.push(x);                       // The result is in the stack 
}

int main(){
    
    string str;
    cin >> str;

    for(int i = 0; i < str.size(); i++){
    
        char c = str[i];
        // Read operand 
        if(isdigit(c)){
    
            int j = i, x = 0;
            while( j < str.size() && isdigit(str[j])){
    
                //j++  Iteration cannot be forgotten  
                x = x *  10 + str[j ++] - '0';   // When the input is not a number but 22 This is greater than 10 Number of numbers , At this point, you need to traverse the whole character , Stop when symbol bit is encountered 
            }
            num.push(x);
            // Because each cycle has i++, We need to point backwards to the last number 
            i = j - 1;
            
        }else if( c == '(' ){
    
            // Mark the , Data in brackets 
            op.push(c);
            
         // Bracket special , When an open bracket is encountered, it is directly put on the stack , If you encounter a closing bracket, calculate the inside of the bracket 
        }else if( c == ')' ){
    
            // Priority of parentheses , Count the parentheses first 
            while( op.size() && op.top() != '(' )   eval();
            // The left bracket can pop up 
            op.pop();
            
        }else{
    
            // You have to calculate the multiplication and division first, and then add and subtract 
            // There must be an equals sign   Our problem is all positive integer calculation 
            // 0 - 5 + 3 
            // If not , The above formula will be miscalculated as  -8
            // The operator to be stacked has low priority , Then calculate first 
            while( op.size() && cmp[op.top()] >= cmp[c])    eval();
            // Put the operator on the stack 
            op.push(c);
        }
    }
  
    while(op.size())    eval();    // Calculate the rest 
    cout << num.top() << endl;     // Output results 
    return 0;
}

This is from the Internet
https://www.acwing.com/solution/content/40978/