逆波兰表达式

 
逆波兰表达式(Reverse Polish Notation)又叫做后缀表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也称为中缀表示。波兰逻辑学家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,+,=
 

计算

 
从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算,并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果.
 

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
while(c != '#')
{
while(isdigit(c)||c=='.')
{
str[i++] = c;
str[i] = '\0';
if(i>=10)
{
printf("出错,数太大!\n");
return -1;
}
scanf("%c",&c);
if(c == ' ')
{
d = atof(str);
push(&s,d);
i = 0;
break;
}

}
switch( c )
{
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);
push(&s,d*e);
break;
case '/':
pop(&s,&e);
pop(&s,&d);
if(e != 0)
{
push(&s,d/e);
}
else
{
printf("\n出错:除数为零!\n");
return -1;
}
break;
}
scanf("%c",&c);
}
pop(&s,&d);
printf("%lf",d);

完整代码
 

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
137
138
139
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef double ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
}sqStack;

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;
}

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++;
}

ClearStack(sqStack *s) //清空栈
{
s->top = s->base;
}

DestroyStack(sqStack *s) //销毁栈
{
int i,len;
len = s->stackSize;
for(i = 0;i<=len;i++)
{
free(s->base);
s->base++;
}
s->base = s->top =NULL;
s->stackSize = 0;
}

int StackLen(sqStack s) //返回栈长度
{
return(s.top - s.base );
}

pop(sqStack *s,ElemType *e) //出栈
{
if(s->top == s->base )
return 0;
*e = *--(s->top);
}

int main()
{
sqStack s;
char c;
double d,e;
char str[10];
int i =0;
InitStack(&s);

printf("请输入表达式 以#结束:");
scanf("%c",&c);

while(c != '#')
{
while(isdigit(c)||c=='.')
{
str[i++] = c;
str[i] = '\0';
if(i>=10)
{
printf("出错,数太大!\n");
return -1;
}
scanf("%c",&c);
if(c == ' ')
{
d = atof(str);
push(&s,d);
i = 0;
break;
}

}
switch( c )
{
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);
push(&s,d*e);
break;
case '/':
pop(&s,&e);
pop(&s,&d);
if(e != 0)
{
push(&s,d/e);
}
else
{
printf("\n出错:除数为零!\n");
return -1;
}
break;
}
scanf("%c",&c);
}
pop(&s,&d);
printf("%lf",d);

return 0;
}

下篇将中缀表达式转换成逆波兰表达式

 

– ©博主原创,转载请注明出处 –

最后更新: 2019年08月21日 14:42

原始链接: https://yuanspace.top/2019/08/20/RPN/

× 请我吃糖~
打赏二维码