ONP - Transform the Expression

题目大意：把表达式转成RPN（Reverse Polish Notation）形式
思路：学过数据结构的估计都知道，一个变量栈，一个运算符栈，运算符优先级不同，低的碰高的要先出栈运算再压栈。
实现：实现是个坎，其实是我想复杂了，我这个是支持a+b*c不带括号的，而这个题都是带括号的，所以代码可以更精简一些。
代码1：

// ONP - Transform the Expression
#include <iostream>
#include <stack>

#define MAXOP 7
using namespace std;
stack<string> vstack;
stack<char> opstack;
#define ADD 1
#define MINUS 2
#define MUL 3
#define DIV 4
#define POW 5

struct operand
{
    char ch;
    int pri;
};

operand ops[] = {
    {'$', 1},
//    {'(', 25},
    {'+', 10},
    {'-', 10},
    {'*', 15},
    {'/', 15},
    {'^', 20},
    {')', 5}};

int ch2pri(char c)
{
    for (int i = 0; i < MAXOP; i++)
    {
        if (c == ops[i].ch)
            return ops[i].pri;
    }
    return 0;
}

void debug() {
    cout << "vstack:" << endl;
    for(stack<string> dump = vstack; !dump.empty(); dump.pop()) {
        cout << dump.top() << endl;
    }
    cout << "opstack:" << endl;
    for(stack<char> dump = opstack; !dump.empty(); dump.pop()) {
        cout << dump.top() << endl;
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    string s, ans;
    while (t--)
    {
        cin >> s;

        // add $ the end of expr
        s.push_back('$');

        // init stacks
        opstack.push('$');

        int len = s.length();
        int i = 0;
        while(i<len)
        {
            if (s[i] >= 'a' && s[i] <= 'z')
            {
                vstack.push(string(1, s[i]));
                //cout <<"var: " << s[i] << endl;
            }else if(s[i] == '(') {
                opstack.push('(');
            }
            else
            {
               // cout << "op: " << s[i] << endl;
                int pri = ch2pri(s[i]);
                if (pri >= ch2pri(opstack.top()))
                {
                    opstack.push(s[i]);
                }
                else
                {
                    char c;
                    if (s[i] == ')')
                    {
                        do
                        {
                            c = opstack.top(); opstack.pop();
                            if (c == '(')
                                break;
                            if (c == '^')
                            {
                                string v = vstack.top(); vstack.pop();
                                vstack.push(v + c);
                            }
                            else
                            {
                                string v2 = vstack.top(); vstack.pop();
                                string v1 = vstack.top(); vstack.pop();
                                vstack.push(v1 + v2 + c);
                            }
                        } while (c != '(');
                    }else if(s[i] == '$') {
                       char c;
                       do {
                           c = opstack.top(); opstack.pop();
                           if(c=='$') break;
                           if(c=='^') {
                                string v = vstack.top(); vstack.pop();
                                vstack.push(v + c);
                               
                           }else {
                                string v2 = vstack.top(); vstack.pop();
                                string v1 = vstack.top(); vstack.pop();
                                vstack.push(v1 + v2 + c);
                               
                           }
                       }while(c!='$'); 
                       break;
                    
                    } else {
                        if (c == '^')
                        {
                            string v = vstack.top(); vstack.pop();
                            vstack.push(v + c);
                        }
                        else
                        {
                            string v2 = vstack.top(); vstack.pop();
                            string v1 = vstack.top(); vstack.pop();
                            vstack.push(v1 + v2 + c);
                        }
                    }
                }
            }
            
            i++;
            //cout << i-1 << endl;
            //debug();
        }
        ans = "";
        while(!vstack.empty()) {
            ans = vstack.top() + ans; vstack.pop();
        }
        cout << ans << endl;
    }
    return 0;
}