栈的典型应用——计算后缀表达式

栈的典型应用——计算后缀表达式

表达式可以分为三种：前缀表达式，后缀表达式，中缀表达式。

  1. 中缀表达式是运算符号在两个数字的之间 也就是我们在数学中常常使用的表达式

  2. 前缀表达式就是在两个数字之前

  3. 后缀表达式就是在两个数字之后，也称为逆波兰表达式

例如计算a+b 后缀表达式就是 a b + ,同理前缀表达式。根据这个意思中缀表达式转换为后缀表达式也就易于理解 a b 也可能是表达式，将a b 之间的字符放在两个表达式之后，而a b 内部的表达式也做相同的操作，这样完成了多层的中缀表达式转成后缀表达式的过程，其实也就是括号法的思想

例如 a+b*c-d+e

中缀 ：((a+(b*c)-(d+e))

后缀：abc*+de+ -

计算机为了便于计算也是利用后缀表达式的方式计算的，而实现这种方法就是利用栈的特性——先进后出 ，来完成后缀表达式的计算

以 6 8 2 * + 5 4 + - 为例 如下图：

在这里插入图片描述

  • 过程： 遇到数字进栈 ，遇到字符弹栈进行计算后进栈，反复执行此过程，完成计算最后将计算结果弹栈。

c语言实现此过程：

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define STACK_SIZE 100
#define INCREMENT 10
#define MAX_SIZE 500
typedef struct stack{
    int  *top;
    int *base;
    int  stacksize;
}sqstack;
void initstack( sqstack *s)
{
    s->base=(int*)malloc(sizeof(sqstack ));
    if(!s->base) exit(0);
    s->top=s->base;
    s->stacksize=STACK_SIZE;
}
void push(sqstack *s, int e )
{
    if(s->top-s->base>=s->stacksize)
    s->base=(int *)realloc(s->base,(s->stacksize+INCREMENT)*sizeof(sqstack));
    *s->top++=e;
}
void pop(sqstack *s, int *e )
{

    if(s->base==s->top) exit(0);
    *e=*--s->top;
}
int isempty(sqstack s)
{
    if(s.base==s.top) return 1;
    else return 0 ;
}
int getstacklength(sqstack s)
{
    return s.top-s.base;
}
int main()
{
    sqstack s ;
    initstack(&s);
    char c ;
    int i =0;
    int e,d;
    int str[MAX_SIZE];
    printf("输入算式 用空格分开数字和字符\n ");

    scanf("%c",&c);
    while(c!='\n')
    {
        while(isdigit(c))
        {
            str[i++]=c;
            str[i]='/0';
            if(i>10)
            printf("error!");
            scanf("%c",&c);
            if(c==' ')
            {
                d=atoi(str);
                push(&s,d);
                i=0;
                break;
            }
        }
        switch(c)
        {
            case '+':
            {
                pop(&s,&e);
                pop(&s,&d);
                push(&s,e+d);
                break;
            }
            case '-':
            {
                pop(&s,&e);
                pop(&s,&d);
                push(&s,d-e);
                break;
            }
            case '*':
            {
                pop(&s,&e);
                pop(&s,&d);
                push(&s,d*e);
                break;
            }
            case '/':
            {
                pop(&s,&e);
                pop(&s,&d);
                if(d==0)
                {
                    printf("error!");
                    exit(0);
                }
                push(&s,e/d);
                break;
            }
        }
        scanf("%c",&c);
    }
    pop(&s,&d);
    printf("%d",d);
    return 0;
}

结果如下
在这里插入图片描述

主要介绍一下计算过程，代码还有许多改进的地方，用了ctype这个库判断是否为数字，通过atoi转化，如果要计算其他类型的话，将栈和数据类型的初始化改为其他类型的数据即可 。