前言

在帮忙同学完成数据结构课设题目–表达式计算时,发现直接从+ - * / 优先级入手的话会比较难完成,因此考虑到先把表达式转换成逆波兰表达式,再用计算逆波兰表达式,这样会比较简单。

不清楚逆波兰表达式和如何将中缀表达式转换成逆波兰表达式的同学可以先阅读这两篇博客:逆波兰表达式计算中缀表达式转换成逆波兰表达式.

波折

当我将中缀表达式转换成逆波兰表达式,将逆波兰表达式存放进数组中,再把数组中的逆波兰表达式作为输入计算时,发现这样做的话,代码就有四五百行了。

禀着能简则简的原则,决定对代码进行简化,最终想到是否可以一边转换成逆波兰表达式一边计算呢,也就是转换和计算同时进行。最后发现想法是可行的。代码量从最初的四百多行简化成一百多行。

成果

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
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
/*  将中缀转后缀表达式 和计算后缀表达式 的算法合并   不定义栈结构体  数组代替栈*/

#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100

double Sum(char a,double x,double y) //两个数的计算
{
switch( a )
{
case '+':
return x+y;
case '-':
return x-y;
case '*':
return x*y;
case '/':
if(y != 0)
{
return x / y;
}
else
{
printf("\n出错:除数为零!\n");
return -1;
}
}
}

int Priority()
{
char s1[STACK_INIT_SIZE]; //运算符存入s1 数字存入s2
double s2[STACK_INIT_SIZE];
char c,e;

double d,f,sum;
char str[10];
int i = 0;

int base1,top1,base2,top2; //分别为s1 和 s2 的 栈顶 栈底

base1=top1=base2=top2 = 0; //初始化栈顶 栈底

scanf ("%c",&c);
while( c != '#')
{
while(c == ' ')
scanf ("%c",&c); //如果接收到空格 则继续输入

while((c >= '0' && c <= '9')||c=='.') //筛选数字
{
str[i++] = c;
str[i] = '\0';
if(i>=10)
{
printf("出错,数太大!\n");
return -1;
}
scanf ("%c",&c);
if(!((c >= '0' && c <= '9')||c=='.')) //数字输入结束
{
d = atof(str); //字符串转换成浮点类型
s2[top2++] = d; //将数字存入 double型的栈中
i = 0;
}
}
while(c == ' ')
scanf ("%c",&c); //如果接收到空格 则继续输入

if(')'==c) //如果遇到 ) 则计算 栈中的数据 直到遇到 (
{
e = s1[--top1]; //运算符出栈
while('(' != e)
{
f = s2[--top2]; //将栈中的两个数字 出栈
d = s2[--top2];
sum = Sum(e,d,f); //计算出栈的两个数
s2[top2++] = sum; //将计算结果存入栈中
e = s1[--top1]; //运算符出栈
}
}
else if('+'==c||'-'==c) //如果遇到 + 或者 - ,就计算栈中的数据 直到运算符栈空
{
if( !(top1 - base1))
{
s1[top1++] = c; //如果运算符栈中无数据 则运算符入栈
}
else //如果运算符栈不为空 则一直计算
{
do
{
e = s1[--top1]; //将栈中的运算符弹出
if('('==e)
{
s1[top1++] = e; //如果 运算符为 ( 入栈
}
else
{
f = s2[--top2]; //将栈中的两个数字 出栈
d = s2[--top2];
sum = Sum(e,d,f); //计算出栈的两个数
s2[top2++] = sum; //将计算结果存入栈中
}
}while(top1 - base1 &&'('!=e);
s1[top1++] = c; //运算符入栈
}
}
else if('*'==c||'/'==c||'('==c) //如果运算符为比较高的 * / 或 ( 就直接入栈等待
{
s1[top1++] = c;
}
else if(c=='#') //遇到 # 说明输入结束 退出循环
{
break;

}
else
{
printf("\n出错:输入格式错误!\n");
return -1;
}

scanf ("%c",&c);
}
//接受完用户输入的所有字符后 不断将数字弹出栈 计算 直到没有运算符 也就是数字只剩最后一个结果
while(top1 - base1)
{
e = s1[--top1];
f = s2[--top2];
d = s2[--top2];
sum = Sum(e,d,f); //计算两个数的结果 并将结果压入栈中
s2[top2++] = sum;
}

d = s2[--top2]; //将最后的结果出栈
if((int)d == d)
printf("\n %d",(int)d); //如果结果为整数就打印整型 如果结果为小数就打印浮点型
else
printf("\n %lf",d);

return 0;
}

int main()
{

char x = 'y';
printf("请输入算数表达式(支持小数),以#作为结束标志:\n");
while(x == 'y')
{
Priority(); //计算

putchar('\n');
printf("\n是否继续输入( y / n )? :");

while((x = getchar()) == '\n'); //清空缓冲区

while(x != 'y' && x != 'n')
{
printf("\n是否继续输入( y / n )? :");

while((x = getchar()) == '\n');
}
while(getchar() != '\n'); //清空缓冲区
putchar('\n');
}
return 0;
}

发现

当完成两种算法的合并时,毅然发现表达式计算算法恰好是根据 + - * / 优先实现计算的。

 

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

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

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

× 请我吃糖~
打赏二维码