简书凉了，这几天挺划水的 = =
黑木华演技真的好，风平浪静的闲暇 真香 = =
横滨流星 一定不是qaq
os、计网 一轮刚结束，PAT还不知怎样 = =
数据结构有PAT的底子应该还好，计组没学过咋整 = =
高数概率论俩月没怎么碰 = =
好，从堂仔的美貌中挣脱了，进入正题——后缀、中缀表达式求值
0902 中午才来图书馆 4l没位置了 在5l一眼就看到了一个神颜哥哥 awsl

后缀表达式求值

对机器而言，后缀表达式求值比中缀表达式求值容易。扫描一遍，O（n）即可。

• 遇操作数，压栈
• 遇运算符，弹出栈顶两个元素，计算并将结果压栈(🤔弹出的依次是操作数2，操作数1 ！！！)

中缀表达式求值

策略：转为后缀表达式，再求值

• 来自ZJU数据结构mooc

例：晴神の模拟题：某计算器的超电磁炮

• ️中缀转后缀
  • 这里的操作数位数不止一位，因此使用空格分割。
  • 当 i >= size 遍历结束， 但操作符栈中可能还留有符号，应逐一pop并添加到后缀表达式末尾。
• ️计算后缀表达式维护一个操作数的栈（必须是stack<double>,中间结果压栈就已经不是int了），遇到符号出栈两个操作数，先出栈的是操作数2，然后操作数1才出栈。
• ️读数字用了while循环来读，记得检查读完数字是不是已经 i >= size了，再执行后面的操作。（e.g. 表达式只有一个数字 123，若不检查就会runtime error，越界访问）
• ️若过程无误，遍历完后缀表达式，num_stack必定刚好留下一个数，即计算结果。

循环中套循环记得检查内部循环之后有没有跳出外层循环的边界，再执行后序操作！！！

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <map>
#include <cstdio>

using namespace std;
map<char, int> op_priority;

string infix2suffix(const string &str) {
    string res;
    stack<char> ops;
    int size = str.size(), i = 0;
    while (i < size) {
        int num_l = 0;
        while (isdigit(str[i])) {
            res += str[i];
            i++;
            num_l++;
        }
        if (num_l) res += ' ';
        if (i >= size) break;
        switch (str[i]) {
            case '(':
                ops.push(str[i]);
                break;
            case ')':
                while (!ops.empty() && ops.top() != '(') {
                    res += ops.top();
                    ops.pop();
                }
                ops.pop(); // pop  (
                break;
            default: // + - * /
                while (!ops.empty() && op_priority[ops.top()] >= op_priority[str[i]]) {
                    res += ops.top();
                    ops.pop();
                }
                ops.push(str[i]);
                break;
        }
        i++;
    }
    while (!ops.empty()) {
        res += ops.top();
        ops.pop();
    }
    return res;
}

double calc_suffix_exp(const string &str) {
    stack<double> num_stack;
    int size = str.size();
    int i = 0;
    while (i < size) {
        int num_l = 0, num = 0;
        while (isdigit(str[i])) {
            num *= 10;
            num += (str[i] - '0');
            i++, num_l++;
        }
        if (str[i] == ' ') i++;
        if (num_l) num_stack.push(num);
        if (i >= size) break;
        if (isdigit(str[i])) continue;
        double op_num2 = num_stack.top(), op_num1;
        num_stack.pop();
        op_num1 = num_stack.top();
        num_stack.pop();
        double temp = 0.0;
        switch (str[i]) {
            case '+':
                temp = op_num1 + op_num2;
                break;
            case '-':
                temp = op_num1 - op_num2;
                break;
            case '*':
                temp = op_num1 * op_num2;
                break;
            case '/':
                temp = op_num1 / op_num2;
                break;
        }
        i++;
        num_stack.push(temp);
    }
    return num_stack.top();
}

int main() {
    op_priority['+'] = op_priority['-'] = 1;
    op_priority['*'] = op_priority['/'] = 2;
    string infix_exp, suffix_exp;
    cin >> infix_exp;
    suffix_exp = infix2suffix(infix_exp);
    printf("%.2lf\n", calc_suffix_exp(suffix_exp));
    return 0;
}

括号匹配

• 扫描每个字符，遇左括号进栈，遇右括号出栈
  • 出栈并检查栈顶是不是与当前右括号匹配的左括号
    匹配则继续，不匹配则退出。
• 扫描结束后，若栈空，则匹配，否则不匹配。