数据结构之线性表-栈之逆波兰表示法-学习笔记-34

引入

在20世纪30年代,波兰逻辑学家扬·卢卡西维茨(Jan Łukasiewicz),发明了一种将所有操作符置于操作数的后面,因此也被称为后缀表示法。我们称之为逆波兰记法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰表示法

上面的引入感觉很高大上,我们来个例题,对于解

$(1-2)\times (4+5)$

连小朋友都知道,先算括号里面的,再算括号外面的,最后结果相乘。
如果计算机来解题的话,就会用很多 if…else… 进行判断,显然对于我们人类方便的括号优先级表达法,对计算机不那么友好。
那么能不能对计算机友好一点?逆波兰表达式出现了,对于上面的问题:

普通式为:$(1-2)\times (4+5)$
逆波兰表达式为:$12-45\times$

基本的转换方法如下

  • 所有数字从左到右写,位置不用动
  • 遇到括号,先写出括号内的数字
  • 然后在数字后面,以先乘除后加减的方式写出括号内的运算符
  • 然后继续写数字,直到所有数字写完
  • 然后在数字后面,以先乘除后加减的方式写出剩余的运算符

几个例子
$a+b$ 转换为:$ab+$
$a+(b-c)$ 转换为:$abc-+$
$a+(b-c) \times d$ 转换为:$abc-d \times+$
$a+b \times (b-c)$ 转换为:$adbc- \times +$

主判断逻辑

栈的创建、初始化、push、pop、length等操作我就不说了,主要讲这个逆波兰的判断。对了,栈内只存符号。
首先判断数字
如果输入的是数字

  • 如果是0~9之间的数字,就直接输出
  • 然后获取下一个输入的值
  • 如果还是数字,就直接输出
  • 如果不是数字,那就输出空格。
  • 这样就完成了判断数字位数的问题。

判断括号

  • 如果输入了反括号,那就证明括号内的内容结束了
  • 我们要把括号内的符号提取出来
  • 没有提取到正括号,那就继续提取里面的符号

判断加减
如果栈内没有符号

  • 输入的如果是加号或者减号
  • 如果栈是空栈,那就压入符号,然后继续接收输入

如果栈内本身有符号

  • 那就先把符号取出来
  • 如果是正括号,那没事,证明要压入的符号是括号内的运算符
  • 直接压入符号即可
  • 如果不是正括号,那就直接把里面的符号输出,因为有新的符号了
  • 判断如果栈不为空并且也不是正括号的话,那就证明栈里面还有运算符,并且这个运算符不是括号内的运算符

判断乘除

  • 如果符号不是+ -,是* / ( 的话
  • 那就直接压栈

判断结束

  • 如果输入的是 # 号的话
  • 那就直接 break 跳出循环

啥都不是

  • 如果输入的是非法字符,则输出错误

继续循环

  • 如果输入的是符号且不是非法字符。
  • 那就继续接收新的值,继续执行循环。

代码实现

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10

typedef char ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;

void InitStack(sqStack *s)
{
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if( !s->base )
exit(0);

s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
}

void Push(sqStack *s, ElemType e)
{
if( s->top - s->base >= s->stackSize )
{
s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if( !s->base )
exit(0);
s->top = s->base + s->stackSize;
s->stackSize = s->stackSize + STACKINCREMENT;
}

*(s->top) = e;
s->top++;
}

void Pop(sqStack *s, ElemType *e){
if( s->top == s->base ){
return;
}
*e = *--(s->top);
}

int StackLen(sqStack s){
return (s.top - s.base);
}

int main()
{
sqStack s;
char c, e;

InitStack( &s );

printf("请输入逆波兰中缀表达式,以#作为结束标志:");
scanf("%c", &c);

//开始判断输入的值,如果不遇到#,就继续接收
while( c != '#' )
{
//判断位数,例如判断1或者11,如果输入的是0~9,则直接打印,然后接一个scanf,判断下一个输入的是数字还是符号,数字就继续输出,符号就输出空格
while( c>='0' && c<='9' )
{
printf("%c", c);
scanf("%c", &c);
if( c<'0' || c>'9' )
{
printf(" ");
}
}

//如果输入的内容是反括号,那就取出栈内的符号,然后直到取出正括号为止,就不输出了,就是输出括号中包含的符号
if( ')' == c )
{
Pop(&s, &e); //把
while( '(' != e )
{
printf("%c", e);
Pop(&s, &e);
}
}
//如果输入的是+或者之一,则执行下面的内容
else if( '+'==c || '-'==c )
{
//如果是空栈,则直接push,记录这个符号
if( !StackLen(s) )
{
Push(&s, c);
}
//如果栈内已经有符号了,先把符号拿出来
else
{
do
{
Pop(&s, &e);
if( '(' == e ) //如果取出来的是括号,那就继续入栈,因为入的是括号内的符号
{
Push(&s, e);
}
else //如果取出来的不是括号,那就先把这个符号输出,因为遇到新符号了
{
printf("%c ", e);
}
}while( StackLen(s) && '('!=e ); //然后判断栈是不是还有东西,并且e不是正括号
Push(&s, c); //然后再把符号压栈
}
}
else if( '*'==c || '/'==c || '('==c ) //如果输入的是*、/或者括号,那就直接压栈,因为反括号的情况判断过了
{
Push(&s, c);
}
else if( '#'== c ) //如果输入的是#号,那就跳出循环
{
break;
}
else //如果输入的不是数字、也不是括号或者四则运算符,那就跳出错误
{
printf("\n格式错误!\n");
return -1;
}

scanf("%c", &c); //如果不是#号,那就继续输入
}

//将栈中的所有内容输出
while( StackLen(s) )
{
Pop(&s, &e);
printf("%c ", e);
}

return 0;
}

尾巴

这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。


-------------The End-------------
欢迎请我喝咖啡哦~!