栈的应用：逆波兰表达式求值

https://blog.csdn.net/ValDC_Morning/article/details/77151550

栈的应用：逆波兰表达式求值
2017年08月13日 23:34:14
阅读数：615

Hello，本篇博客Val主要来给大家分享一下栈的一个用途：逆波兰表达式求值。

逆波兰表达式也叫后缀表达式，先操作数，后操作符。
栈 后进先出 ，顺序遍历波兰表达式，遇到操作数的时候入栈 ， 遇到操作符，先让操作数出栈运算操作数，然后再把运算结果入栈，所有的算式都可以用逆波兰表达式写出来。

把算式12*(3+4)-6+8/2+2用逆波兰表达式写出来，就是 12 3 4 + * 6 - 8 2 / +2 +
逆波兰表达式也叫后缀表达式，有的题目会给你一个算术表达式，求出它的后缀表达式。

如图：逆波兰表达式的操作数入栈运算方式、遇到操作符进行运算后将结果压入栈

这里写图片描述

#pragma once

#include
#include
#include
using namespace std;

enum Type
{
    OP_NUM,
    OP_SYMBOL,
    ADD,
    SUB,
    MUL,
    DIV,
};
struct Cell
{
    Type _type;
    int _value;
};

int CountRPN(Cell *rpn, size_t n)//
{
    stack s;
    for (size_t i = 0; i < n; i++)
    {
        if (rpn[i]._type == OP_NUM)//是操作数  入栈
        {
            s.push(rpn[i]._value);
        }
        else//遇到了操作符
        {
            int right = s.top(); //右操作数在左操作数之后入栈
            s.pop();
            int left = s.top();//左操作数
            s.pop();
            switch (rpn[i]._value)//看它是哪个操作符，就执行哪个，把结果再放入栈中
            {
            case ADD:
                s.push(left + right);
                break;
            case SUB:
                s.push(left - right);
                break;
            case MUL:
                s.push(left * right);
                break;
            case DIV:
                s.push(left / right);
                break;
            }
        }
    }
    assert(s.size() == 1);//最后结束时，栈里应该只有一个数据，为最终结果
    return s.top();//返回栈顶数据（最终结果）
}
//12*(3+4)-6+8/2+2
int main()
{
    Cell RPN[] =
    {
        { OP_NUM, 12 },
        { OP_NUM, 3 },
        { OP_NUM, 4 },
        { OP_SYMBOL, ADD },
        { OP_SYMBOL, MUL },
        { OP_NUM, 6 },
        { OP_SYMBOL, SUB },
        { OP_NUM, 8 },
        { OP_NUM, 2 },
        { OP_SYMBOL, DIV },
        { OP_SYMBOL, ADD },
        { OP_NUM, 2 },
        { OP_SYMBOL, ADD },

    };
    cout << sizeof(RPN) << " " << sizeof(Cell) << endl;
    cout << "结果：" << CountRPN(RPN, sizeof(RPN) / sizeof(Cell)) << endl;
    system("pause");
    return 0;
}

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83

　　关于栈的运用：逆波兰表达式就分享到这里啦！
　　逆波兰表达式同过栈对其操作（遇到操作数入栈，遇到操作符，运算栈里的数据，再将其放回栈中），这样运算结束后，如果运算正确，栈中只有一个数据（也是栈顶数据），就是算术表达式的值。

https://blog.csdn.net/u010785685/article/details/40477933

软考习题里遇到了这样一道题，给出了一个逆波兰式，让求它对应的中缀表达式。

逆波兰式：ab-cd+* ,它的中缀表达式是（a-b）*(c+d)

 

思考：

这让我蒙圈了，这是为什么呢。怎么得到的呢，应该有什么规律的吧。

 

首先我们要知道：

 

波兰式：前缀表达式

逆波兰式：后缀表达式

 

了解这三个表达式之前，我们需要知道

 

表达式	解释	例子
前缀	不含括号的的算数表达式，将运算符写在前面，操作数写在后面	*+ 2 1 3
中缀	必须含括号，操作符处于操作数的中间	(2+1)*3
后缀	不含括号，运算符放在两个运算对象的后面。	3 2 + 3 *

 

    这三个表达式的重点就是他们之间的转换，学会转换，对这三个表达式也就了解的差不多了，那么到底怎么转换的呢？

给出一个中缀表达式，转化为前缀和后缀表达式。

例如我们做的这道题，中缀表达式答案是（a-b）*(c+d)，我们看来验证一下他正确不。

步骤：

第一步：按照运算符的优先级，对所有的运算单位加括号。

                 （（a-b）*（c+d））

第二步转换：

                      转换为前缀：把运算符号移动到对应的括号前面，然后去掉括号。

                      

                     “*”移最前面；“-”移到  -（ab）;“+”移到+（cd）

                    得到：*-(ab)+(cd)去括号后：*-ab+cd

                       转换为后缀：

                     “*”移到最后；“-”移到（ab）-;“+”移到（cd）+

                    得到：(ab)-(cd)+*去括号后：ab-cd+*

   以上方法适用于较为简单的选择题，对于真正的算法题我觉得就给多想想了。

   对于前缀、中缀和后缀的知识不仅是是他们的转化，还有很多知识，以后会再了解的。

   而对于逆波兰式，冲着这么好听的名字，也得明白他是什么吧，其实就是波兰逻辑学家的一个人发明的一种表示表达式的方式。这种表示法的优点就是根据运算对象和算符的出现次序进行计算,便于用栈实现求值。

   只学会了简单的转换，对于这方面的认识还远远不够，其实中缀表达式转化为后缀表达式也是数据结构里的一个算法题。逆波兰表达式只用于两种简单操作，入栈和出栈。按顺序扫描逆波兰表达式，如果当前字符是变量或者数字就压栈，如果是运算符，则将栈顶两个元素弹出想想运算，结果再入栈，最后当表达式扫描完后，栈里就是结果。

     个人理解的不是很深刻，具体到算法题估计还是有一定的困难，不过走一步算一步，能理解多少是多少。这个算法会不会考也不知道，不总结就更不认识了。先总结了再说，有什么错误请大家指点，互相交流。