acwing 3302. Expression evaluation

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 231−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 105.

sample input ：
(2+2)*(1+1)
sample output ：
8

The key ：
Two stacks are required , A stack is used to store numbers , Another is to save the operation operator

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;  //  Save digital stack 
stack<char> op;  //  Save the operator stack 

void eval()
{
    
    auto b = num.top(); num.pop();  //  Take the number 
    auto a = num.top(); num.pop();  //  Take the number 
    auto c = op.top(); op.pop();    //  Take operator 
    int x;

	//  Calculation 
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    
    unordered_map<char, int> pr{
    {
    '+', 1}, {
    '-', 1}, {
    '*', 2}, {
    '/', 2}};  //  If there is ^,  You can add  {'^',3}
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
    
        auto c = str[i];
        if (isdigit(c))  //  Digital stack 
        {
    
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0'; 
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')')
        {
    
            while (op.top() != '(') eval();  //  Always need to calculate to the left bracket 
            op.pop();
        }
        else
        {
    
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval(); //  Priority saved in the stack  >=  Current priority 
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}