SPOJ Transform the Expression 逆波兰式算法题解

把带括号的一般正常的算式，转换成逆波兰式。

输入和输出如下例子：

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

总结规律是很困难的事情，总结好就能很快解决：

1 字母直接放结果

2  ‘（’入栈

3 ‘）’ 出栈到‘（’，然后出栈‘（’

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

4 操作符比较，高优先级的全部出栈，入结果，操作符入栈

#include <iostream>
#include <string>
#include <queue>
#include <stack>
using namespace std;  

int opToint(char op)
{
    if ('+' == op) return 0;
    if ('-' == op) return 1;
    if ('*' == op) return 2;
    if ('/' == op) return 3;
    if ('^' == op) return 4;
    return -1;
}  

bool cmpOP(char a, char b)
{
    return opToint(a) - opToint(b) < 0;
}  

string handleRPN(string &express)
{
    string ans;
    stack<char> stk;
    for (int i = 0; i < express.size(); i++)
    {
        if ('a' <= express[i] && express[i] <= 'z') ans.push_back(express[i]);
        else if ('(' == express[i]) stk.push(express[i]);
        else if (')' == express[i])
        {
            while (!stk.empty() && '(' != stk.top())
            {
                ans.push_back(stk.top());
                stk.pop();
            }
            if (!stk.empty() && '(' == stk.top()) stk.pop();
        }
        else
        {
            while (!stk.empty() && '(' != stk.top() &&
                !cmpOP(stk.top(), express[i]) )
            {
                ans.push_back(stk.top());
                stk.pop();
            }
            stk.push(express[i]);
        }
    }
    return ans;
}  

void TransformTheExpressionToRPN()
{
    string express;
    int T = 0;
    cin>>T;
    while (T--)
    {
        cin>>express;
        cout<<handleRPN(express)<<endl;
    }
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索string
， include
， return
， if
， express
， 操作符
逆波兰式
逆波兰式算法、逆波兰式算法 java、逆波兰式算法c、逆波兰式、编译原理逆波兰式，以便于您获取更多的相关知识。