题目链接

将中缀表达式转化为后缀表达式。

数字的话直接放到答案的字符串里。

如果是左括号就进栈， 右括号就让栈里的符号都出来直到第一个左括号。

否则的话比较当前符号的优先级和栈顶符号的优先级。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <complex>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef complex <double> cmx;

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9+7;

const int inf = 1061109567;

const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

map <char, int> sign;

vector <char> ans;

void solve() {

    ans.clear();

    stack <char> st;

    string s;

    cin>>s;

    int last = 6;

    for(int i = 0; i < s.size(); i++) {

        char c = s[i];

        if(isalnum(c)) {

            ans.pb(c);

        } else {

            if(c == '(') {

                st.push(c);

                last = 6;

            } else if(c == ')') {

                char tmp;

                tmp = st.top();

                st.pop();

                do {

                    ans.pb(tmp);

                    tmp = st.top();

                    st.pop();

                } while (tmp != '(');

                last = 6;

            } else {

                if(sign[c]>=last) {

                    ans.pb(c);

                 } else {

                    st.push(c);

                    last = sign[c];

                 }

            }

        }

    }

    for(auto &i: ans) {

        cout<<i;

    }

    cout<<endl;

}

void init() {

    sign['+'] = 1;

    sign['-'] = 2;

    sign['*'] = 3;

    sign['/'] = 4;

    sign['^'] = 5;

}

int main()

{

    init();

    int t;

    cin>>t;

    while(t--) {

        solve();

    }

    return 0;

}