后缀表达式或者逆波兰表达式(栈实现)

最新推荐文章于 2023-10-27 10:31:13 发布

杨小乐coder

最新推荐文章于 2023-10-27 10:31:13 发布

阅读量255

点赞数

分类专栏： C & C++ 算法

本文链接：https://blog.csdn.net/yanxiaole_coder/article/details/111589570

版权

本文介绍了后缀表达式（逆波兰表达式）的概念，详细阐述了如何通过栈结构求后缀表达式的值，并讨论了如何将普通表达式转换为后缀表达式，提到了迪杰斯特拉的调用场算法。同时，通过实例展示了表达式3!+4*2/(1-5)^2的转换和求值过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

后缀表达式或者逆波兰表达式(栈实现)

3!+4*2/(1-5)^2 转换成后缀表达式: 3 ! 4 2 * 1 5 - 2 ^ / +
不难发现，后缀表达式完全舍弃了表达式本该有的可读性，但有失必有得，相比普通表达式，后缀表达式的值可以轻松借助栈存储结构求得。具体求值的过程是：当用户给定一个后缀表达式时，按照从左到右的顺序依次扫描表达式中的各个运算项和运算符，对它们进行如下处理：

遇到运算项时，直接入栈；
遇到运算符时，将位于栈顶的运算项出栈，对于 ! 运算符，取栈顶 1 个运算项；其它运算符，取栈顶 2 个运算项，第一个取出的运算项作为该运算符的右运算项，另一个作为左运算项。求此表达式的值并将其入栈。

经过以上操作，直到栈中仅存在一个运算项为止，此运算项即为整个表达式的值。

以3 ! 4 2 * 1 5 - 2 ^ / +表达式为例，求值的过程为：

从 3 开始，它是运算项，因此直接入栈：
! 作为运算符，从栈顶取 1 个运算项（也就是 3），求 3! 的值（3! = 321=6）并将其入栈：

在这里插入图片描述

将 4 和 2 先后入栈：
对于 * 运算符，取栈顶 2 个运算项（ 2 和 4），其中先取出的 2 作为 * 的右操作数，4 作为左操作数。求的 4* 2 的值 8 ，并将其入栈：
将 1 和 5 先后入栈：

在这里插入图片描述

对于 - 运算符，取栈顶 2 个运算项（5 和 1），计算出 1-5 的值为 -4，将其入栈：
将 2 入栈：
对于 ^ 运算符，取栈顶 2 个运算项（2 和 -4），计算出 -4^2 的值 16 ，将其入栈：
对于 / 运算符，取栈顶 2 个运算项（16 和 8），计算出 8/16 的值 0.5，将其入栈：
对于 + 运算符，取栈顶 2 个运算符（0.5 和 6），计算出 6+0.5 的值 6.5，将其入栈：

由此，整个求值的过程就结束了，最终表达式的值为 6.5。如下给出了实现此过程的参考代码：

//根据给定的后缀表达式 postexp，计算它的值
typedef struct
{
   
    double data[MAXSIZE];
    int top;
}Stack_num;

void InitStack_num(Stack_num **s)
{
   
    *s = (Stack_num *)malloc(sizeof(Stack_num));
    (*s)->top = -1;
}

bool Push_num(Stack_num **s, double e)
{
   
    if ((*s)->top == MAXSIZE - 1)
        return false;
    (*s)->top++;
    (*s)->data[(*s)->top] = e;
    return true;
}

bool Pop_num(Stack_num **s, double *e)
{
   
    if ((*s)->top == -1)
        return false;
    *e = (*s)->data[(*s)->top];
    (*s)->top--;
    return true;
}

//计算后缀表达式的值
double compvalue(char *postexp)
{
   
    Stack_num *num;
    int i = 1;
    double result;
    double a, b;
    double c;
    double d;
    InitStack_num(&num);
    //依次扫描整个表达式
    while (*postexp != '\0')
    {
   
        switch (*postexp)
        {
   
            case '+':
                Pop_num(&num, &a);
                Pop_num(&num, &b);
                //计算 b+a 的值
                c = b + a;
                Push_num(

最低0.47元/天解锁文章