栈不仅可以用来计算后缀表达式的值，而且我们还可以用栈将一个标准表达式（或叫中缀式inifx）转换成后缀式，我们可以通过只允许操作+,*, (,)并坚持普通的优先级法则而将一般的问题浓缩成小规模的问题，我们还要进一步假设表达式是合法的。设我们想要把中缀表达式:

a + b * c + (d * e + f) * g

转换成后缀表达式，正确的答案是：

a b c * + d e * f + g * +

这里我们有两个栈，一个是放符号的符号栈，一个是放后缀表达式的输出栈

当读到一个操作数的时候，立即把它放到输出栈中。操作符不立即放入输出栈中输出，而放入符号栈中。 如果见到一个右括号，那么就将符号栈中的元素弹出，将弹出的符号写入到输出栈中直到我们遇到一个（对应的）左括号，但是这个左括号只被弹出，并不输输入到输出粘中。 如果我们见到任何其他的符号（+， * , (,），那么我们从符号栈中弹出栈元素直到发现优先级更低的元素为止。有一个例外：除非是在处理一个“）”的时候，否则我们绝不从栈中移走“（”。对于这种操作，“+”的优先级最低，而“（”的优先级最高。当从符号栈弹出元素的工作完成后，我们再将操作符压人符号栈中。 最后，如果我们读到输入的末尾，我们将栈元素弹出直到粘变成空栈，将符号写到输出中。

与前面相同，这种转换至于要O（N）时间并经过一趟输入后工作完成。我们可以通过指定减法和加法有相同的优先级以及乘法和除法有相同的优先级而将减法和除法添加到指令集中。

代码实现如下：

#include <iostream>#include <stack>#include <vector>using std::cout;using std::endl;using std::string;using std::vector;using std::stack;int getPrioprty(const char chr){    switch (chr)    {        case '+':         case '-': return 1;        case '*':        case '/': return 2;        case '(': return 3;                default:            return 0;    }}stack<char> InfixtoPostfix(const string &InfixStr){    stack<char> operStack;    stack<char> outputStack;    for(const auto &item: InfixStr){        cout << "item: " << item << endl;        if(item == ' '){            continue;         }        else if(item == '+' || item == '-' || item == '*' || item=='/' || item == '('){            if(operStack.empty()){                operStack.push(item);            }            else{                while (getPrioprty(item) <= getPrioprty(operStack.top())){                    if(getPrioprty(operStack.top()) == 3){                        break;                    }                    else{                        outputStack.push(operStack.top());                        operStack.pop();                        if(operStack.empty()) break;                    }                }                operStack.push(item);            }        }        else if(item == ')'){            while(operStack.top() != '('){                outputStack.push(operStack.top());                operStack.pop();            }            operStack.pop();        }        else{            outputStack.push(item);        }    }    cout << "done" << endl;    while (!operStack.empty()){        outputStack.push(operStack.top());        operStack.pop();    }    return outputStack;}int main(int argc, char const *argv[]){    string infixStr = "a + b * c + (d * e + f) * g";    string expected = "abc*+de*f+g*+";    string outputStr;    stack<char> output = InfixtoPostfix(infixStr);    while(!output.empty()){        outputStr.insert(0, 1, output.top());        output.pop();    }    cout << outputStr << endl;    cout << std::boolalpha << (outputStr == expected) << endl;    return 0;}