表达式求值-408数据结构

转载

2023 年 09 月 23 日

359 次浏览

暂无评论

1974字数

转载

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

**注意：**

* 数据保证给定的表达式合法。
* 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-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)`

### 输出样例：

### 题目分析

栈 逆波兰表达式 括号匹配

### 代码实现

```
#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;
} 
```

最后修改：2023 年 09 月 23 日