题解 BNDS OJ 1263 表达式求值

简要题意：

输入一个表达式，包括 +，-，*，/，(，)。求出表达式的值，保留两位小数（不知道你谷有没有这道题）。

提供一组样例：

样例输入： 

1
9-(6+3*5)/3

样例输出：

1
2.00

策略分析：

这不是简单的数据结构入门题，我们只需要拿两个栈，一个存数字一个存运算符，碰到后括号就把它到前括号里的值全部算出来。因为在这6个运算符中，除了括号其他均是二元运算符，所以符号栈栈顶运算符（除了括号）一定匹配数字栈的头两个数字 ，按照运算优先级取出来算就可以了。运算优先级我们可以用一个 来处理，具体细节见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <unordered_map>
#include <stack>
#include <iomanip>
#define LD long double
using namespace std;

namespace SHAWN {
    unordered_map<char, int> pri;
    stack<LD> dig;
    stack<char> ope;
    string s;
    void calcu() {// 出栈计算
        LD a = dig.top(); dig.pop();
        LD b = dig.top(); dig.pop();
        char opt = ope.top(); ope.pop();
        LD res = 0;
        if (opt == '+') { res = b + a; }
        if (opt == '-') { res = b - a; }
        if (opt == '*') { res = b * a; }
        if (opt == '/') { res = b / a; }
        dig.push(res);// 算完的结果塞回数字栈
    }
    int work()
    {
        pri['+'] = pri['-'] = 1;
        pri['*'] = pri['/'] = 2;
        cin >> s;
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            if (isdigit(s[i])) {// 遇到数字就存进栈里
                int x = 0, j = i;
                while (j < len && isdigit(s[j])) {
                    x = x * 10 + s[j] - '0';
                    j++;
                }
                dig.push(x);
                i = j - 1;
            }
            else if (s[i] == '(') { ope.push(s[i]); }// 左括号进栈
            else if (s[i] == ')') {// 遇到右括号就一直向前算到上一个左括号
                while (ope.top() != '(') { calcu(); }
                ope.pop();
            }
            else {// 遇到运算符直接按优先级进行计算
                while (ope.size() && pri[ope.top()] >= pri[s[i]]) { calcu(); }
                ope.push(s[i]); 
            }
        }
        while (ope.size()) { calcu(); }// 完成剩余计算
        cout << fixed << setprecision(2) << dig.top() << '\n';// 最后的结果就是数字栈栈顶元素，保留两位输出即可
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}