博客

给定一个表达式，其中运算符仅包含

+,-,*,/

（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

• 数据保证给定的表达式合法。
• 题目保证符号
  
-

  只作为减号出现，不会作为负号出现，例如，
  
-1+2

  ,
  
(2+2)*(-(1+1)+2)

  之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 231−1.
• 题目中的整除是指向 00 取整，也就是说对于大于 00 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。
• C++和Java中的整除默认是向零取整；Python中的整除
  
//

  默认向下取整，因此Python的
  
eval()

  函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 10e5。

输入样例：

(2+2)*(1+1)

输出样例：

8

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

using namespace std;

stack<int> num;
stack<char> op;


unordered_map<char ,int> pr={{'+',1},{'-',1},{'/',2},{'*',2}};
void evel()
{
   auto x=num.top();num.pop();
   auto y=num.top();num.pop();
   auto z=op.top();op.pop();
   
   if(z=='+')num.push(x+y);
   if(z=='-')num.push(x-y);
   if(z=='*')num.push(x*y);
   if(z=='/')num.push(x/y);
}

int main()
{
    string s;
    cin>>s;
    
    for(int i=0;i<s.size();i++)
    {
        if(isdigit(s[i]))
        {
            int j=i;
            int sum=0;
            while(j<s.size()&&isdigit(s[j]))sum=sum*10+s[j++]-'0';
            i=j-1;
            num.push(sum);//如果是数字就入栈
        }
        else if(s[i]=='(')   op.push(s[i]);
        else if(s[i]==')'){
            while(op.top()!='(') evel();//如果是有括号就把括号内的所有元素从右到左计算
            // （3*5+1）该情况下3*5会被下一个else 提前计算出来，所以括号内右边的运算符总是大于左边
            op.pop();
        }
        else {
            while(op.size()!=0&&pr[op.top()]>=pr[s[i]])evel();//如果栈顶运算符优先级大于或等于要入栈的运算符则
             op.push(s[i]);                                              //计算，否则入栈
                                                           
            
            
        }
        
    }
    while(op.size()) evel();//把从左到右清空栈
    cout<<num.top();
    
}