后缀表达式的计算

作者: 芒果和小猫 | 来源:发表于2017-12-06 19:38 被阅读0次

    1、栈

    栈是一种只允许一端操作的线性数据结构,具有LIFO(last in first out)的特点,具有广泛的应用,如我在游戏编程模式--命令模式(2)中使用栈的结构来实验撤销、重做功能。现在打算用栈结构来实现后缀表达式的计算。

    2、后缀表达式

    后缀表达式,指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。

    例如 5+(2+3)*4 转换为后缀表达式为 523+4*+

    3、后缀表达式的计算

    规则:从左向右扫描,遇到数字压栈,遇到操作符,弹出栈顶的两个元素,先弹出的元素在右边,后弹出来的在左边,进行计算后,将结果压栈,再往后扫描,直到扫描结束,输出栈顶元素,即为最终结果。
    523+4*+为例
    5压栈 2压栈 3压栈 遇到+号,弹出3 2,计算2+3,将5压栈,此时栈为5 5,将4压栈,遇到*号,弹出4 5,计算5*4,将20压栈 此时栈为5 20 ,遇到+号,计算5+20,将25压栈,扫描结束,输出25。
    以上就是计算过程。下面用C++编写代码,为了方便标记算式的结束,在末尾我们加上#,用来标识算式结束,这里我们只进行四则运算

    #include <iostream>
    #include <stack>
    #include "string"
    using namespace std;
    
    int main()
    {
        stack<int> a;
        string temp;
        cin >> temp;
        int i = 0;
        while (true)
        {
            if (temp[i]=='#') cout << a.top(); break;
            if (temp[i]<='9'&&temp[i]>='0') a.push(temp[i]-48);
            else
            {
                int x, y;
                y = a.top(); a.pop();
                x = a.top(); a.pop();
                switch (temp[i])
                {
                case '+':a.push(x + y); break;
                case '-':a.push(x - y); break;
                case '*':a.push(x * y); break;
                case '/':a.push(x / y); break;
                default:break;
                }
            }
            ++i;        
        }
        cin >> temp;
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:后缀表达式的计算

        本文链接:https://www.haomeiwen.com/subject/hqvlixtx.html