-

2021年1月30日发(作者：周星驰年)
题目

：算术表达式求值问题

内容

：

一个算术表达式是由操作数

(operand)
、运算符

(operator)
和界限符

(delimiter)
组成

的。

假设操
作数是正整数，

运算符只含加减乘除等四种运算符，

界限符有左右括号和表达式

起始、结束符“
#
”，如：

#
(
7+15
)
*
(
23-28/4
)
#
。引入表达式起始、结束符是为了方便。

编程利用“算符优先法”求算术表达式的
值。要求：
(
1
)
从键盘读入一个合法的算术表达

式，输出正确的结果。
(
2
)
显示输入序列和栈的变化过程。选作内容：操作数类型扩充到

实数。

一：问题分析和任务定义

1.
问题分析：

分析题目并参考书目可以基本了解完成一个算术表达式所存在的问题。对一个表达式

来说，

由于各种运算符和界限符的运用，

运算符和界限符的优先级决定了算术表达式不是简

单的从左往右的运算。
因 此设计算法完成算术表达式时就要考虑各运算符和界限符的优先

级，

同时还要注意操作数与算符的判断。

在算法中要求完成操作数、

运算符和界限符的出入

栈，运算符和界限符的优先级比较和操作数之间的运算。

最后完成的算法要求输入一个算术

表达式，

能够正
确的计算出来它的最后结果并输出。

为了不用考虑算符优先级，

将输入的中

缀表达式转换成后缀表达式。

这样就可以知道实现本程序需要进行的操作：

1)
2)
3)
4)
建立空栈，存储信息；

运用函数实现出入栈和取栈顶元素操作。

将中缀表达式转换成后缀表达式。

实现后缀表达式的求解。

5)
建立一个函数使中缀表达式能够被有效输入。

本程序的关键是中缀表达式转换成后缀表达式

对于
栈的操作
(
1
)
建空栈

setStack()
运算的结果是将栈顶元素返回。

(
2
)
清空栈

(
3
)
入栈

EmptyStack
()
，可以用于判断栈内元素的有无，在栈顶元素的输出被使用。

push
(),
出栈
pop()
和取栈顶元素
top()
。

2.
任务定义

1)
．

本演示程序中，利用栈将输入的中缀表达式转换成后缀表达式，并完成其求解过程来

达到计算表达式的目的。

2)
．

演示程序以用户和计算机的对话方式执行，即在计算机终端上显示

果显示在其后。


提示信息


之后，

由用户在键盘上输入演示程序中需要输入的数据，以“回车符”为结束标志。相应的输

入数据和运算结
3)
．

程序执行的命令包括：

1)
输入任意一个整数表达式；

2
)
是否继续。

4)
．

测试数据

输入一个整数表达式：

3+
(
5*8-9
)
输出：

后缀表达式：

3 5 8 *9 -+
结果为：

34
继续？
(
y/n
)
二、数据结构的选择和概要设计

算术表达式中各数据元素间存在一种线性关系，设计的数据类型如下：

#define MAXNUM 50
typedef int DataType;
typedef struct {
DataType s[MAXNUM];
int t;
}SeqStack,*PSeqStack;//
定义一个类型名为

SeqStack
的数据类型

本算法设计过程中只采用加减乘除
等四种运算符，

题目要求借助栈完成算法设计，

提示

中要把中缀表达式转换成后 缀表达式计算，因此操作运
算包括要建空栈、清空栈、进栈、出

栈、取栈顶元素，中 缀表达式转换成后缀表达式，后缀表达式的运算等。
将运算符和界限符

一起描述为算符，本程序的设计如下：

(
1
)
先定义一下数据结构来存储算术表达式。

(
2
)
建空栈
setstack(),
清空栈。

(
3
)
对栈进行的运算函数，出入栈和取栈顶元素。

(
4
)
中缀表达式转换成后缀表达式的函数

its
()
。

(
5
)
后缀表达式计算函数。

(
6
)
设计存放后缀表达式的队列。

(
7
)
主函数

main(),
使得整个程序完整进行。

三、详细设计和编码

为了实现概要设计中的所有数据类型，对每个操作给出算法。对主程序和其他模块也

都需要写出算
法。

1
)
数据类型

#define MAXNUM 50
typedef int DataType;
typedef struct {
DataType s[MAXNUM];
int t;
}SeqStack,*PSeqStack;
〃定义一个类型名为

SeqStack
的数据类型

建空栈和其它关于栈的操作

这部分为栈的运算问题。为后面表达式转换和计算做准备。这方面的知识书上有系统

讲到，不需要过
多去设计算法。

2
)
表达式的转换和计算

将中缀表达式转换成后缀表达式，

顺序扫描中缀算术表达式，

当读到数字时直接将起送

至输出队列
中；

当读到运算符时，

将栈中所有优先级高于或等于该运算符的运算符弹出，

送

至输出 队列中，再将当前
运算符入栈；当读入左括号时，即入栈；当读入右括号时，将靠近

栈的第一个左括号上面的运算符依次弹出，

送至输出队列中，

再删除栈中左括号。

在计算后

缀表达式式，最后保存的值是最先取出参与运算，所以要用
到栈。

读到数字时直接送至输出队列中：

switch(c1) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
set =1;
suffix[j++]=c1; /*
遇到数字输出

*/
break;
当读到左括号时入栈：

case '(':
set=0;
push(ps, c1); /*
遇到左括号，入栈

*/
break;
当读入右括号时，
将靠近栈的第一个左括号上面的运算 符依次弹出，
送至输出队

列中，
再删除栈中左括号：

case ')':
c2 = ')'; /*
遇到右括号把右括号赋值给

c2*/
while(!EmptyStack(ps)) { /*
当栈不为空时

*/
c2=top(ps); /*
遇到右括号取栈顶

*/ pop(ps);
/
*
出栈

*/
if(c2 =='(')
break; /*
遇到左括号时停止出栈

*/
suffix[j++]=c2; /*c2
的值放入后缀表达式中

*/
}
当读到加减乘除号时，栈和后缀表达式的变化。因为优先级的关系，将加减号

同时考
虑，乘除号同时考虑。读到加减号处理时运用算法如下：

case '+': case '-':
while(!EmptyStack(ps)) { /*
当栈不为空时

*/ c2 = top(ps); /*
将栈顶元素赋值给

c2*/ if(c2
=='+'|| c2 =='-'|| c2 == '*' || c2 == '/') {
pop(ps); /*
遇到加减号时栈中栈顶元素是加减乘除四种运算符出栈

*/ suffix[j++] =
c2; /*
将

c2
放入后缀表达式中

*/
}

else if(c2=='(')
break; /*
遇到加减号时栈顶元素是左括号不进行出栈

*/

}

push(ps, c1); /*c1
入栈

*/
break;
读到乘除号处理时算法与加减法基本一致，

但在

if
语句时只需考虑

c2 == '*' || c2 == '/'
。

计算后缀表达式时读到数值时计算

sum
的值

switch(c) { case '0': case '1': case '2': case '3':
case '4': case '5': case '6': case '7': case '8': case '9':
if(set == 1) /*
遇到操作数

*/ sum = sum * 10 + c - '0'; /*sum
的计算

*/ else /*
所遇
到的不是操作数

*/ sum = c - '0';/*sum
的计算

*/
set=1; break;
考虑遇到空格、制符表和运算符时

sum
值的入栈情况

case ' ': case't': case 'n':
if (set == 1) { push(ps, sum); /*
遇到空格或制表符

sum
入栈

*/ set = 0; }
break;
case '+':
case '-':
case '*':
case '/': if(set == 1) { push(ps, sum); /*
遇到运算符时

sum
入栈

*/ set = 0; }
遇到加减乘
除四个运算符时将栈顶和次栈顶元素分别运用所遇到运算符进行运算，

并将运算结果入栈

num2 = top(ps); /*
栈顶元素赋值给

num2*/ pop(ps); /*
元素出栈

*/
if(EmptyStack(ps)) { /*
当栈为空

*/ free(ps); /*
释放栈内空间

*/ return 0;
}

num1 = top(ps); /*
栈顶元素赋值给

num1*/ pop(ps); /*
元素出栈

*/ if(c == '+') { /*c
为加
号时

*/
push(ps, num1 + num2); /*num1
与

num2
的和入栈

*/
}

if(c == '-') { /*c
为减号时

*/
push(ps, num1 - num2); /*num1
与

num2
的差入栈

*/
}

if(c == '*'){ /*c
为乘号时

*/
push(ps, num1 * num2); /*num1
与

num2
的积入栈

*/
}

if(c == '/'){ /*c
为除号时

*/
push(ps, num1 / num2); /*num1
与

num2
的商入栈

*/
}

break;
default:
free(ps);
return 0; }
}

}
该部分为程序的核心算法，即将算术表达式的值正确的输出。

4)
主函数

基本的数据定义，并实现表达式的输入，并调用

getline()
函数

void main() {
char c, infix[MAXNUM], suffix[MAXNUM];
int result;
int flag = 1; while(flag == 1) {
printf(
请输入任意一个整数算术表达式

:n
getline(infix, MAXNUM);
if(its(infix, suffix) == 1) {
printf(
所得后缀为

:%sn
}

/*
调用

getline()
函数

*/
else {
printf(
无效缀

!n
}

调用

calculateSuffix()
函数使程序完整

if(calculateSuffix(suffix, &result) == 1){ /*
调用

calculateSuffix()
函数

*/ printf(
结果
为

:%dn
}

else {
printf(
非法后缀

!n
}

四、上机调试


1•
编程中遇到的几个问题

刚看到题目的时候，我对题意没有理解，运用的普通的方法来完成程序，运行时输入无括
号的算术表达式
可以正确输出结果，但输入带括号的表达式时输出的结果与运算结果不符。

因此根据提示，设计算法将输入的
中缀表达式转换成后缀表达式再运算得到结果。在此算法
即最终使用的程序中，中缀表达式转换成后缀表达式
函数中

2
、算法设计、调试的经验和体会

刚
开
始
拿到
这
个
问
题
时
自
己
对
如何
设
计
算
法
没
有
一
点
头绪
。
但
我
从
中
理
解
了
题目
的
意

最重要的是启发了我运用本课程中所学的去解决该问题。

我

思，也找到了解决问题的思路，

做
设计一个程序需要按一个完整的步骤来进行。

首先必须弄懂


完本次实验还有一个体会是：

程序要解决的是什么问题。在弄懂之后大脑中就要开始构思要用是什么方法来解决问题，

多

问同学、老师或者多查阅相关资料通过网络等等。

只有经过这个过程才会提高自己的发现问

题、分析问题、解决问题的能力，使得思维更加严谨。虽然这次课程设计不是很难，不是做

一个比较大的系
统，

代码不算多，但是我认为要成功地完成一个程序，

都要投入必要的时间和精力，认真对待，这样我们可以收获不少东西。

通过这次课程设计，

我深知自己学习的知识还远远不够。

基础。我们网络工程专业就要跟大量的程序算法打交道。

的时候，才能运用的得心应手，恰到好处。

五、测试结果及其分析

这是一种全面综合训练，

是与

这就要求我们必须

包括完整的实验报告

课堂听讲，自学和练习相辅相成的，

必不可少的一个教学环节。

这次的课程设计为以后的学

习打下了 坚实的
将每一句语言的精髓领悟透彻，注重细节，掌握每一种算法的功能。只有这样，我们在解决

实际生活中的问题
1
、运行程序后，初界面
:

图
1
:
运行程序后初界面

2
、输入表达式后
:




























3
、输入


































图
2
:
输入表达式后

y
后
:
图
3
:
输入
y
后

4
、再次输入表达式
:






























5
、输入
n
后
:
































图
4
:
再次输入表达式

图
5
:
输入
n
后

6
、在初始界面后输入
#
时
:

-

-

-

-

-

-

-

-