带括号的四则运算

题目描述

给定一个数学表达式，求结果。表达式中只包含‘+’, ‘-’, ‘*’, ‘/’, ‘(’, ‘)’。

示例

输入：5 - (6 - 2) * 4 / 8

输出：3

思路

中缀表达式转为后缀表达式
1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2
2. 从左至右扫描中缀表达式
3. 遇到操作数时，将其压入S2
4. 遇到运算符时，比较其与S1栈顶运算符的优先级：
  1. 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈
  2. 否则，若优先级比栈顶运算符的高，也将运算符压入S1(注意必须是高，相同和低于都不行)
  3. 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4.1)与S1中新的栈顶运算符相比较
5. 遇到括号时：
  1. 如果是左括号“(”，则直接压入S1
  2. 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2,直到遇到左括号为止，此时将这一对括号丢弃
6. 重复步骤(2)至(5)，直到表达式的最右边
7. 将S1中剩余的运算符依次弹出并压入S2
8. 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
计算后缀表达式
1. 从左向右扫描
2. 遇到数字，压入栈中
3. 遇到运算符，弹出栈顶的两个数，并用运算符对这两个数做相应的计算，并将结果入栈
4. 重复上诉2、3步骤，直到表达式的最右端，最后的值即为表达式的结果

Code

#include <algorithm>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <vector>
using namespace std;

bool isOp(char c) {
    switch (c) {
        case '+':
        case '-':
        case '*':
        case '/':
            return true;
        default:
            return false;
    }
}

bool isP(char c) {
    return c == '(' || c == ')';
}

int priorityCompare(char a, char b) {
    map<char, int> mp;
    mp['+'] = 1;
    mp['-'] = 1;
    mp['*'] = 2;
    mp['/'] = 2;
    return mp[a] - mp[b];
}

int calSimple(int a, int b, char c) {
    switch (c) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        default:
            return 0;
    }
}

// 中缀表达式转后缀表达式
vector<string> infix2suffix(string s) {
    int sz = s.size();
    stack<char> op;
    stack<string> sk;
    // 针对  1 - (-2)  这种情况
    // flag为true表示读完了'('但尚未读到运算符
    bool flag = false;

    for (int i = 0; i < sz; ++i) {
        if (s[i] >= '0' && s[i] <= '9') {
            flag = false;
            int t = 0;
            while (i < sz && s[i] >= '0' && s[i] <= '9') {
                t *= 10;
                t += (s[i] - '0');
                ++i;
            }
            --i;
            sk.push(to_string(t));
        } else if (isOp(s[i])) {
            if (flag) {
                if (s[i] == '+' || s[i] == '-') {
                    sk.push("0");
                }
            }
            flag = false;
            while (true) {
                if (op.empty() || op.top() == '(' ||
                    priorityCompare(s[i], op.top()) > 0) {
                    op.push(s[i]);
                    break;
                } else {
                    string str(1, op.top());
                    sk.push(str);
                    op.pop();
                }
            }
        } else if (isP(s[i])) {
            if (s[i] == '(') {
                flag = true;
                op.push(s[i]);
            } else {
                flag = false;
                while (op.size() && op.top() != '(') {
                    string str(1, op.top());
                    sk.push(str);
                    op.pop();
                }
                if (op.top() == '(') {
                    op.pop();
                }
            }
        }
    }
    while (op.size()) {
        string str(1, op.top());
        sk.push(str);
        op.pop();
    }
    vector<string> vec;
    while (sk.size()) {
        vec.push_back(sk.top());
        sk.pop();
    }
    reverse(vec.begin(), vec.end());

    return vec;
}

// 后缀表达式(逆波兰表达式)求值
int calReversePolishNotation(vector<string> v) {
    stack<int> t;
    for (int i = 0; i < v.size(); ++i) {
        if (v[i][0] >= '0' && v[i][0] <= '9') {
            t.push(stoi(v[i]));
        } else {
            int first = 0, second = 0;  // 因为有"-1+2"这种，所以置0
            if (t.size()) {
                second = t.top();
                t.pop();
            }
            if (t.size()) {
                first = t.top();
                t.pop();
            }
            t.push(calSimple(first, second, v[i][0]));
        }
    }
    return t.size() ? t.top() : -1;
}

int main() {
    freopen("../00input.txt", "r", stdin);

    string s;
    getline(cin, s);
    vector<string> vec = infix2suffix(s);
    cout << calReversePolishNotation(vec) << '\n';
    return 0;
}

补充

前缀、中缀、后缀表达式对应其二叉树的前序、中序、后序遍历结果