写在前面：LeetCode刷题笔记

---

中序表达式转后序表达式（从左向右读入）

1. 创建一个队列，存储后缀表达式；创建一个栈，存储操作符。

2. 遇到操作数则送入队列。

3. 遇到 “(“ ，入栈，遇到操作符入栈。

4. 如果遇到其他运算符，不断去除所有运算优先级大于等于当前运算符的运算符，送入队列。最后，新的符号入栈。

5. 遇到 “)” 括号，则将栈内从 “(“ 到 “)” 的所有操作符全部取出送入队列（左括号出栈但不入队）。

6. 中序表达式读取结束后，如果栈不为空，则将栈内元素依次出栈送入队列。

7. 此时队列的表达式即为原中序表达式的后序表达式。

/*代码实现中将操作数队列替换为vector*/
/*代码实现中只考虑了加、减运算，故没有判断优先级，如果是一个四则运算表达式可以添加优先级判断部分*/
void inToPost(string s, vector<char>& post)
{
    //vector<char> post;
    stack<char> op;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '(')
        {
            op.push(s[i]);
        }
        else if (s[i] == '+')
        {
            while (!op.empty() && (op.top() == '+' || op.top() == '-'))
            {
                char tmp = op.top();
                op.pop();
                post.push_back(tmp);
            }
            op.push(s[i]);
        }
        else if (s[i] == '-')
        {
            while (!op.empty() && (op.top() == '+' || op.top() == '-'))
            {
                char tmp = op.top();
                op.pop();
                post.push_back(tmp);
            }
            op.push(s[i]);
        }
        else if (s[i] == ')')
        {
            while (!op.empty() && op.top() != '(')
            {
                char tmp = op.top();
                op.pop();
                post.push_back(tmp);
            }
            op.pop();
        }
        else
        {
            post.push_back(s[i]);
        }
    }
    while (!op.empty())
    {
        post.push_back(op.top());
        op.pop();
    }
}

参考文章：表达式求值