数据结构-栈应用之逆波兰表达式（后缀表达式）

迈不过友情╰ 2022-05-12 13:20 240阅读 0赞

逆波兰表达式含义我就不做赘述了，摘自百科上的一段话：

逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。  
逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。这个知识点在数据结构和编译原理这两门课程中都有介绍，下面是一些例子：  
正常的表达式 逆波兰表达式  
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,+,=

用途

逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)\*(c+d)转换为ab+cd+\*

优势

它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下：  
如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。

以上红线为划重点，如果没理解这句话的意思，那么接下来的代码就不用看了（无奈~~）

//
    // Created by Administrator on 2018/5/28.
    //
    
    //逆波兰表达式（后缀表达式）
    
    #include "stdio.h"
    #include "stdlib.h"
    #include "string.h"
    
    #define ElementType int
    #define MaxSize 20
    
    //定义栈的结构体
    typedef struct {
        ElementType *top;//栈顶指针（这里定义为指向栈顶元素的下一个位置，即为空）
        ElementType *base;//栈底指针
        int stackSize;//栈的容量
    } Stack;
    
    /**
     *  初始化栈
     * @param s
     */
    void InitStack(Stack *s) {
        //初始化分配栈的总空间
        s->base = (ElementType *) malloc(MaxSize * sizeof(ElementType));
        if (!s->base) {
            //分配失败
            printf("初始化分配空间失败!");
            exit(0);
        }
        s->top = s->base;
        s->stackSize = MaxSize;
    }
    
    /**
     * 入栈
     * @param s 栈
     * @param e 入栈元素
     */
    void Push(Stack *s, ElementType e) {
        //判断栈是否已满
        if (s->top - s->base >= s->stackSize) {
            //栈已满
            //处理方式1.递增空间 2.退出
            printf("栈已满~\n");
            exit(0);
        }
        *(s->top) = e; //赋值
        s->top++;
    }
    
    /**
     * 出栈
     * @param s 栈
     * @return
     */
    ElementType Pop(Stack *s) {
        //判断栈是否为空
        if (s->base == s->top) {
            //栈为空
            //printf("\n不好意思，栈目前为空~\n");
            return -1;
        }
        s->top--;
        ElementType e = *(s->top);//取值，并不是取地址
        return e;
    }
    
    /**
     * 栈当前容量
     * @param s
     * @return
     */
    ElementType GetLen(Stack s) {
        int len = (s.top - s.base);
        return len;
    }
    
    int main() {
        //存在中缀表达式：1+2*(4-3)+6/6
        //转换为后缀表达式：1234-*+66/+
        char exp[] = {'1', '2', '4', '3', '-', '*', '+', '6', '6', '/', '+'};
        Stack stack;
        InitStack(&stack);
        int len = strlen(exp);
        int length = sizeof(exp) / sizeof(exp[0]);
        for (int i = 0; i < length; i++) {
            char p = exp[i];
            int temp;
            ElementType a;
            ElementType b;
            switch (p) {
                case '+':
                    a = Pop(&stack);
                    b = Pop(&stack);
                    temp = b + a;
                    Push(&stack, temp);
                    break;
                case '-':
                    a = Pop(&stack);
                    b = Pop(&stack);
                    temp = b - a;
                    Push(&stack, temp);
                    break;
                case '*':
                    a = Pop(&stack);
                    b = Pop(&stack);
                    temp = b * a;
                    Push(&stack, temp);
                    break;
                case '/':
                    a = Pop(&stack);
                    b = Pop(&stack);
                    if (b == 0) {
                        printf("除数不能为0~\n");
                        return -1;
                    }
                    temp = b / a;
                    Push(&stack, temp);
                    break;
                default:
                    temp = p - 48;
                    Push(&stack, temp);
                    break;
            }
        }
        char sum = Pop(&stack);
        printf("\n表达式计算结果 value=%d\n", sum);
    }

![70][]

[70]: /images/20220504/6734da2a23fc4250b95cb59bbcb26c27.png