首页 > 代码库 > 栈的应用 — 逆波兰记法

栈的应用 — 逆波兰记法

逆波兰记法又称为后缀记法,把操作符放置于操作数后面,计算过程通常用栈来实现的,通过栈来保存中间结果,使得逆波兰记法没有必要知道任何优先规则。

方法描述:当见到一个数时就把它推入栈中;在遇到运算符时该运算符就作用于从该栈弹出的两个数上,将结果推入栈中。

下面演示计算后缀表达式的过程。
后缀表达式:6 5 2 3 + 8 * + 3 + *
四个数字入栈:6 5 2 3(→栈生长方向)
读到“+”,2、3出栈,相加,结果入栈:6 5 5
读到“8”,入栈:6 5 5 8
读到“*”,5、8出栈,相乘,结果入栈:6 5 40
读到“+”,5、40出栈,相加,结果入栈:6 45
读到“3”,入栈:6 45 3
读到“+”,45 3出栈,相加,结果入栈6 48
读到“*”,6、48出栈,相乘,结果入栈288

计算一个后缀表达式花费的时间是O(N),每个元素都只进行一些栈操作,而这些栈操作只花费常数时间。

下面是自己写的代码,只能应用于整型的加减乘除四则运算。由于需要字符和数字的相互转换,比较蛋疼,果断选择了C++来写:
#include <iostream>
#include <vector>
#include <stack>
#include <ctype.h>
#include <cstdlib>
#include <sstream>
 
using namespace std;
 
bool IsDigit(string str)
{
    for(int i = 0; i < str.size(); i++)
        if ((str.at(i) > ‘9‘) || (str.at(i) < ‘0‘))
            return false;
    return true;
}
 
int main()
{
    stack<string> s;
    string input;
 
    while (cin >> input)
    {
        if (IsDigit(input))
            s.push(input);
        else if ((input == "+") || (input == "-") || (input == "*") || (input == "/"))
        {
            int lhs = atoi((s.top()).c_str());
            s.pop();
            int rhs = atoi((s.top()).c_str());
            s.pop();
 
            stringstream ss;
            string midval;
            switch (*input.c_str())
            {
                case ‘+‘ :
                    ss << (lhs+rhs);
                    ss >> midval;
                    s.push(midval);
                    break;
                case ‘-‘ :
                    ss << (lhs-rhs);
                    ss >> midval;
                    s.push(midval);
                    break;
                case ‘*‘ :
                    ss << (lhs*rhs);
                    ss >> midval;
                    s.push(midval);
                    break;
                case ‘/‘ :
                    ss << (rhs/lhs);    // 注意除法的操作数有顺序限制
                    ss >> midval;
                    s.push(midval);
                    break;
            }
        }
    }
 
    cout << s.top();
 
    return 0;
}


至于怎么从中缀表达式转换成后缀表达式,见另一篇“栈的应用 — 中缀式转后缀式”。

参考:
《数据结构于算法分析》 P52.