中缀表达式转后缀表达式(带括号优先级)

中缀表达式转后缀表达式(带括号优先级)

#include<iostream>
#include<stack>
#include<unordered_map>

using namespace std;

int main() {
    char c;
    stack<char> st;
    unordered_map<char, int> mp; // 运算符优先级
    mp['+'] = mp['-'] = 0;
    mp['*'] = mp['/'] = 1;
    mp['('] = mp[')'] = 2;
    unordered_map<char, int> symbol_cnt; // 记录括号数量
    bool isblank = false;
    while (scanf("%c ", &c) != EOF) {
        if ('0' <= c && c <= '9') { //假设输入的操作数只有一位
            if (isblank) printf(" ");
            else isblank = true; 
            printf("%c", c);
        } else {
            if (c == '(') symbol_cnt['('] += 1; // 记录是否存左右括号，以调整运算符的出栈顺序
            if (c == ')') symbol_cnt[')'] += 1;
            if (c == ')') { // 若遇到右括号，则一直出栈直到遇到左括号
                while (st.top() != '(') {
                    printf(" %c", st.top());
                    st.pop(); 
                }
                st.pop();
                symbol_cnt['(']--; // 一对括号中的运算表达式转换完成。括号数量还原
                symbol_cnt[')']--;
            }
            while (!st.empty() && mp[c] <= mp[st.top()]) {
                if (st.top() == '(' && symbol_cnt['('] != symbol_cnt[')']) { 
                    // 如果栈顶为左括号，则左括号之前的运算符暂时不输出。（先运算括号里边的式子）
                    break;
                }
                printf(" %c", st.top());
                st.pop();
            }
            if (c == ')') continue; // 右括号不入栈
            st.push(c);
        }
    }
    while (!st.empty()) {
        printf(" %c", st.top());
        st.pop();
    }
    return 0;
}

// input: 3 + 4 * ( 5 - 6 + 3 / 6 ) + 7 - 9 * 5 / ( 3 + 2 - 1 * 3 ) + 6
// output: 3 4 5 6 - 3 6 / + * + 7 + 9 5 * 3 2 + 1 3 * - / - 6 +