栈在表达式求值中的应用

1. 逆波兰表达式求值
2. 前缀表达式求值
3. 中缀表达式转逆波兰式
4. 编程

1. 逆波兰表达式求值

思路：因为逆波兰式将运算符写在操作数之后，即 E1 E2 op（例如 5 8 +）。所以碰到op，只用把op前面两个数（或者计算结果）直接拿来运算即可。充分利用栈的后进先出的特点，过程如下：

遇到数字就将数字压栈
遇到操作符，就将栈顶的两个元素取出计算，将计算结果再压入栈。

举例说明，对于中缀表达式 (3+4) x 5 - 6，其后缀表达式为 3 4 + 5 × 6 -。其计算步骤如下：

从左至右扫描后缀表达式，将3和4压入堆栈；
遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
将5入栈；
接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
将6入栈；
最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

代码示例：

#include <iostream>
#include <stack>
#include <string>
#include <cstdlib> //atoi()
using namespace std;

int evaluate_rpn(string tokens[], int n)
{
    stack<int> s;
    for (int i = 0; i < n; i++)
    {
        string t = tokens[i];
        if (t.compare("+") == 0 || t.compare("-") == 0 || t.compare("*") == 0 || t.compare("/") == 0)
        {
            //第二个数值
            int b = s.top();
            s.pop();
            //第一个数值
            int a = s.top();
            s.pop();

            //计算结果，并压回堆栈。
            if (t == "+")
                s.push(a + b);
            else if (t == "-")
                s.push(a - b);
            else if (t == "*")
                s.push(a * b);
            else
                s.push(a / b);
        }
        else //遇到数值，直接压到堆栈中
        {
            s.push(atoi(t.c_str())); //string类型可以用.c_str()转成char*
        }
    }
    return s.top();
}
int main()
{
    string tokens[] = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
    int len = sizeof(tokens) / sizeof(tokens[0]); //字符串长度
    cout << evaluate_rpn(tokens, len) << endl;
    return 0;
}

2. 前缀表达式求值

参考逆波兰表达式思考。可以选择从后往前扫描。

顺序扫描的过程稍微复杂一点。

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

//判断是否为运算符号
bool is_op(string t)
{
    return t.compare("+") == 0 || t.compare("-") == 0 || t.compare("*") == 0 || t.compare("/") == 0;
}

//该方法使用从前往后扫描的方式，也可以从后往前扫描更简单。
string evaluate_pn(string tokens[], int n) 
{
    stack<string> s;
    for (int i = 0; i < n; i++)
    {
        string t = tokens[i];
        if (is_op(t))
        {
            s.push(t);
            continue;
        }

        while (!is_op(t) && s.size() > 0 && !is_op(s.top()))
        {
            //第一个数值
            int a = atoi(s.top().c_str());
            s.pop();
            //第二个数值
            int b = atoi(t.c_str());
            //两个数值的前面，必定为运算符
            string op = s.top();
            s.pop();
            //计算结果。
            int ret = 0;
            if (op == "+")
                ret = a + b;
            else if (op == "-")
                ret = a - b;
            else if (op == "*")
                ret = a * b;
            else
                ret = a / b;
            //转换为字符串，压入栈中
            stringstream ss;
            ss << ret;
            t = ss.str();
        }
        s.push(t);//前面不是数字了，将计算结果压回堆栈
    }
    return s.top();
}

int main()
{
    string tokens[] = {"*", "+", "5", "*", "3", "-", "9", "5", "/", "8", "2"};
    int len = sizeof(tokens) / sizeof(tokens[0]);
    cout << evaluate_pn(tokens, len);
    return 0;
}

3. 中缀表达式转逆波兰式

中缀表达式转换为后缀表达式的思路。

遍历中缀表达式中的数字和符号
1. 对于数字：直接输出
2. 对于符号：
  1. 左括号：进栈
  2. 符号：与栈顶符号进行优先级比较
    1. 栈顶符号优先级低：进栈
    2. 栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
  3. 右括号：将栈顶符号弹出并输出，直到匹配左括号
遍历结束：将栈中的所有符号弹出并输出

1. 逆波兰表达式求值

2. 前缀表达式求值

3. 中缀表达式转逆波兰式

4. 编程