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

注意:

  • 数据保证给定的表达式合法。
  • 题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
  • 题目保证表达式中所有数字均为正整数。
  • 题目保证表达式在中间计算过程以及结果中,均不超过 $2^{31}-1$。
  • 题目中的整除是指向 0 取整,也就是说对于大于 0 的结果向下取整,例如 $5/3=1$,对于小于 0 的结果向上取整,例如 $5/(1-4)=-1$。
  • C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。

输入格式

共一行,为给定表达式。

输出格式

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

数据范围

表达式的长度不超过 $10^5$。

输入样例:

(2+2)*(1+1)

输出样例:

8

题目分析

栈 逆波兰表达式 括号匹配

代码实现

#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
using ll = long long;

string s;
stack <ll> nums;
stack <char> ops;
unordered_map <char, int> w = {
    {'+',1},{'-',1},{'*',2},{'/',2}  
};
inline void eval () {
    auto op = ops.top(); ops.pop();
    auto b = nums.top(); nums.pop();
    auto a = nums.top(); nums.pop();
    switch (op) {
        case '+':
            nums.push(a + b);
            break;
        case '-':
            nums.push(a - b);
            break;
        case '*':
            nums.push(a * b);
            break;
        case '/':
            nums.push(a / b);
            break;
    }
}
inline bool isCalculate (char op) {
    return op == '+' || op == '-' || op == '*' || op == '/';
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    getline(cin,s);
    for (int i = 0; i < (int)s.length(); ++i) {
        if (isdigit(s[i])) {
            int t = 0;
            while(i < (int)s.length() && isdigit(s[i])) t = t * 10 + (s[i++] - '0');
            nums.push(t);
            --i;
        }
        else if (s[i] == '(') ops.push(s[i]);
        else if (s[i] == ')') {
            while(ops.top() != '(') eval();
            ops.pop();
        }
        else {
            while(i < s.length() && ops.size() && w[ops.top()] >= w[s[i]]) eval();
            ops.push(s[i]);
        }
    }
    while(ops.size()) eval();
    cout << nums.top();
    return 0;
} 
分类: DFSStackTree

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status