逆波兰表达式(后缀表达式)

     逆波兰表达式,它的语法规定,表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。下面是一些例子:

我们提供的服务有:成都网站建设、网站制作、微信公众号开发、网站优化、网站认证、于都ssl等。为上千多家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的于都网站制作公司

正常的表达式 逆波兰表达式

a+b ---> a,b,+

a+(b-c) ---> a,b,c,-,+

a+(b-c)*d ---> a,b,c,-,d,*,+

a+d*(b-c)--->a,d,b,c,-,*,+

a=1+3 ---> a=1,3 +

   通过后缀表达式计算表达式值的过程:顺序访问表达式的每一项,若该项为操作数,则将其压入栈中;若该项是操作符,则连续从栈中退出两个操作数X和Y,形成运算指令XY,将其结果重新压入栈中。当表达式的每一项都访问并处理,则其计算结果就是当前栈顶存放的值。

逆波兰表达式(后缀表达式)

   下面我们以表达式4+3*4+3*(1+5)———>434*+315+*+

逆波兰表达式(后缀表达式)

源程序:

#pragma once
#include
#include
#include
using namespace std;

enum Type
{
    OP_NUM,
    OP_SYMBOL,
};

enum SYMBOL
{
    ADD,
    SUB,
    MUL,
    DIV,
};
struct Cell
{
    Type _type;
    int _value;
};
double CountRNP(Cell *a, size_t size)
{
    assert(a);
    stack s;
    double right = 0;
    double left = 0;
    for (size_t i = 0; i < size; i++)
    {
        if (a[i]._type == OP_NUM)
        {
            s.push(a[i]._value);
        }
        else
        {
            if (s.empty())
            {
            return 0;
            }
            right = s.top();
            if (s.empty())
            {
            return 0;
            }
            s.pop();
            left = s.top();
            s.pop();
            switch (a[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:
                if (left== 0)
                    {
                        cout << "error" << endl;
                    }
                else
                    {
                       s.push(right / left);
                    }    
                break;
            }
        }
    }
    return s.top();
}

测试代码:

#include"calculate.h"
int main()
{
    Cell a[] = { { OP_NUM, 4 }, { OP_NUM, 3 }, { OP_NUM, 4 },
    { OP_SYMBOL, MUL }, { OP_SYMBOL, ADD }, { OP_NUM, 3 }, { OP_NUM, 1 }
    , { OP_NUM, 5 }, { OP_SYMBOL, ADD }, { OP_SYMBOL, MUL }, { OP_SYMBOL, ADD } };
    size_t size = sizeof(a) / sizeof(a[0]);
    cout << CountRNP(a, size) << endl;
    system("pause");
    return 0;
}

结果:

逆波兰表达式(后缀表达式)


网站名称:逆波兰表达式(后缀表达式)
本文路径:http://scyanting.com/article/iphjsh.html