Fork me on GitHub

简单中缀表达式求值

这是很久很久之前写的一个小作业,利用栈实现的一个简单中缀表达式求值,所谓前缀、中缀、后缀,是指运算符相对于运算数的位置而言。这个是中缀,所以实现其实很简单 ,只有加、减、乘、除以及括号的四则运算,大致思路是定义了两个栈:操作符栈和操作数栈,顾名思义,操作符用于存放运算符,操作数用于存放运算数字。代码如下:

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
140
141
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
/**
* 操作栈的相关定义
*/
typedef struct
{
char *elem;
int top;
int size;
}Sqstack;
//定义操作符栈和操作数栈
Sqstack Ope;
Sqstack Num;

void Initstack(Sqstack *s) //初始化栈
{
s->size=50;
s->top=0;
s->elem=(char*)malloc(s->size*sizeof(char));
if(!s->elem)
printf("OVERFLOW");
}

void Push(Sqstack *s,char e) //入栈
{
if(s->top>=s->size)//栈内存不够时
{
char *newelem;
int increment=50;
newelem=(char*)realloc(s->elem,(s->size+increment)*sizeof(char));
s->elem=newelem;
s->size=s->size+increment;
}
s->elem[s->top]=e;
s->top++;
}

void Pop(Sqstack *s)//出栈
{
s->top--;
}

char GetTop(Sqstack *s)//取栈顶元素
{
char e;
s->top--;
e=s->elem[s->top];

return e;
}
void calculate(Sqstack *ope,Sqstack *num)
{

char num1,num2,op;
num2=GetTop(num);
num1=GetTop(num);
op=GetTop(ope);
int tmpResult=0;
switch(op)
{
case '+':
tmpResult=num1+num2;
break;
case '-':
tmpResult=num1-num2;
break;
case '*':
tmpResult=num1*num2;
break;
case '/':
tmpResult=num1/num2;
break;
}
Push(num,tmpResult);//入栈
}
void dealExpression()
{
Initstack(&Ope);
Initstack(&Num);
printf("请输入正确的中缀表达式(以#号结束):");
char onechar; //单个字符
scanf("%c",&onechar);
while(onechar!='#')
{
switch(onechar)
{
case '+':
case '-':
if(Ope.top&&Ope.elem[Ope.top-1]!='(')
{
calculate(&Ope,&Num);
}
Push(&Ope,onechar); //入栈
scanf("%c",&onechar);
break;
case '*':
case '/':
if(Ope.top&&(Ope.elem[Ope.top-1]=='*'||Ope.elem[Ope.top-1]=='/'))
{
calculate(&Ope,&Num);
}
Push(&Ope,onechar); //入栈
scanf("%c",&onechar);
break;
case '(':
Push(&Ope,onechar); //入栈
scanf("%c",&onechar);
break;
case ')':
while(Ope.elem[Ope.top-1]!='(')//当前是')',则Ope栈一定能有'('匹配到,即Ope栈一定不为空
{
calculate(&Ope,&Num);
}
Pop(&Ope);//出栈,弹出左括号
scanf("%c",&onechar);
break;
default://onechar为数字,则入num栈
char opNum=0;
do{
opNum=opNum*10+onechar-'0';
scanf("%c", &onechar);
}while(onechar>='0' && onechar<='9');
Push(&Num,opNum);
break;
}//end switch
}//end while
while(Ope.top)
{
calculate(&Ope,&Num);
}
int result;
result=Num.elem[Num.top-1];
printf("计算结果是%d\n", result);
}
int main()
{
dealExpression();
return 0;
}
-------------Page's overThanks for reading-------------

本文标题:简单中缀表达式求值

本文作者:SherlockYang

发布时间:2018年11月21日 - 17:11

最后更新:2018年12月18日 - 20:12

原始链接:https://sherlock-y.com/2018/11/21/简单中缀表达式求值/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

如果文章内容对你有帮助,就赏博主一瓶维他奶吧~