逆波兰表示法——栈

什么是逆波兰表示法？

逆波兰表示法是一种将运算符写在操作数后面的描述程序（算式）的方法。

举个例子，我们平常用中缀表示法描述的算式（1 + 2）* （5+ 4），改为逆波兰表示法之后则是1 2 + 3 4 - *。

相较于中缀表示法，逆波兰表示法的优势在于不需要括号。

 

给定一个逆波兰表达式，试求其值并输出。

思路：

将这个逆波兰表达式（说白了就是字符串）存入strinng str中，然后遍历这个str的每个字符。

 

（1）如果出现计算符号加减乘除，那么就取出栈中的前两个元素进行计算。这里需要特别注意的是，栈是后进先出，所以第一个出来的是中缀表示法下计算符号右边的那个数！而除法和减法不满足交换律！所以这里要特别小心。具体见代码。

（2）如果出现的是数字，那么，考虑到这个数字可能是多位数（比如123），所以我们还要再看一下str的这个数字之后的字符是否为数字。如果是，那么就：更新后的值 = 原来的值 × 10 + 原来的字符后面的这单个数字的值.

举个栗子（就不给你吃）

12 = 1 * 10 + 2; 12的最前面的数字为1，之后是2. 12 = 1 * 10 + 2

123 = ((1*10)+2)*10 + 3; 类比上面的12

这里，我们用ans来记录数字的值。ans初始化为0

（3）如果出现的是空格，那么检查ans这个记录是否为0.

如果ans == 0，那么就不理它。

否则，将ans压入栈中，并更新ans，将其再次更新为0，以便进行下一次多位数（也可能是个位数）数值的计算。

（4）如果遍历到字符串的末尾，那么就输出栈中剩下的值。这时因为之前肯定是计算了一个值与另一个值的匀速之后的结果，然后压入栈中。所以这时，栈中只剩下这一个值了，而这个值，显然是答案：因为所有的计算过程都模拟完了。

 

例题:试求逆波兰表达式的值

Input

10 20 + 374 375 - *

Output

-30

Hint

(10 + 20) * (374 - 375) = 30 * (-1) = -30

 

根据上述思路（包含代码的解释），C++代码实现如下：

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

int main()
{
    stack<int> s;

    int a, b;
    string str = "10 20 + 374 375 - *"; // (10 + 20) * (374 - 375) = 30 * (-1) = -30
    int num;
    int ans = 0;
    // cin >> str;

    for (unsigned int i = 0; i < str.length(); i++)
    {
        if (str[i] == '+')
        {
            a = s.top();  s.pop();
            b = s.top();  s.pop();
            s.push(b + a); 
        }
        else if (str[i] == '-')
        {
            a = s.top();  s.pop();
            b = s.top();  s.pop();
            s.push(b - a);
        }
        else if (str[i] == '*')
        {
            a = s.top();  s.pop();
            b = s.top();  s.pop();
            s.push(b * a); 
        }
        else if (str[i] == '/')
        {
            a = s.top();  s.pop();
            b = s.top();  s.pop();
            if (a == 0)
            {
                cout << "Invalid!\n";
                return 0;
            }
            else
            {
                s.push(b / a);
            }
        }
        else if (str[i] == ' ')
        {
            if (ans != 0)
            {
                s.push(ans);
            }
            ans = 0; // 更新ans，以便计算下一个数值
        }
        else // 将字符串片段转化为整数
             //先将每一个字符转化为个位数，然后每增加一位数字，在原来数字的基础上乘10加上这个数
        {
            num = str[i] - '0'; //先将每一个字符转化为个位数
            ans = ans * 10 + num; //每增加一位数字，在原来数字的基础上乘10加上这个数:比如123 = ((1*10)+2)*10 + 3;
        } 
    }

    printf ("%d\n", s.top());

    return 0;
}

纸上得来终觉浅，绝知此事要躬行。