《带括号算术表达式的计算》实验报告


四川学
数结构算法分析实验报告











实验名称 ：带括号算术表达式求值
指导老师 ：_______________________
学 院 ：_______软件学院_______
专 业 ：_______软件工程_______
姓 名 ：________ _____
学 号 ：_____ ____
班 级 ：___________ 班________
日 期 ：___2014年X月X日___


目录



实验题目 3

二 实验目求 3

三 实验环境 3

四 算法描述 3

五 源程序清单 附录

六 运行结果 6

七 实验运行情况分析 7




实验题目
l 带括号算术表达式求值
二实验目求
ü 采算符优先数算法正确求值表达式
ü 熟练掌握栈应
ü 熟练掌握计算机系统基操作方法解编辑编译链接运行C程序
ü 机调试程序掌握查错排错程序正确运行
三实验环境
² 硬件环境
联想 笔记电脑
² 软件环境
操作系统 windows 7 旗舰版
编译软件Visual C++ 60
四算法描述
否
开始


判断表达式否正确
键盘读入算术表
达式存入单链表中

栈计算显示算数表达式

退出程序


否继续计算？
显示错误信息
否
Ø 程序框图








判断表达式否正确



Ø 文字解释
1 户键盘读入算术中缀表达式结尾
2 程序判断户输入表达式否正确
3 表达式正确栈计算算术表达式
4 印输出计算程终结果
5 程序询问户否继续计算
6 继续执行第1步否定退出程序
7 表达式错误印错误信息提示户重新输入
8 返回第1步
Ø 函数结构说明
l 结构体
1) 存储算数表达式单链表
struct Expression{
char sign
struct Expression *next
}

2) 操作符操作数栈
typedef struct{
char *top
char *bottom
int stack_size
}Stack

l 构造函数
1) 栈相关操作函数
① 初始化空栈 int StackCreate(Stack *s)
② 入栈操作 int PUSH(Stack *s char c)
③ 出栈操作 int POP(Stack *s char c)
④ 获取栈顶元素 char GetTop(Stack *s)

2) 计算相关操作函数
①利栈计算算术表达式 int Calculate(struct Expression *exp)
②子式值计算 int Count(char num1 char sign char num2)
③判断字符否运算符 int IsOpOrNum(char c)
④判断运算符优先级 char JudgeLevel(char c1 char c2)
⑤判断表达式正确性 int IsExpresiion(struct Expression *exp)
⑥输出计算结果 void PrintResult(struct Expression *expint result)

3) 算术表达式输入函数
①键盘读入存单链表 struct Expression *GetExp()

符号2
l 构造操作符优先级表
符号1
较

+

*

(
)
(#)
+
>
>
<
<
<
>
>

>
>
<
<
<
>
>
*
>
>
>
>
<
>
>

>
>
>
>
<
>
>
(
<
<
<
<
<


)
>
>
>
>

>
>
(#)
<
<
<
<
<



五源程序清单
Ø 见附录
六运行结果
Ø 测试表
l 次测试采户键盘输入算数表达式进行16组测试

序号
测试功
测试容
输入项
预期输出
实际输出
结果
1
基计算操作
单括号运算
2*(3+4)+5*3
29
29
通
2
基计算操作
括号运算
3+((4+3)*6)3
17
17
通
3
基计算操作
整运算
6*(2+(32))
21
18
误差
4
基计算操作
整运算
(1+2+3)4
15
1
误差
5
式子正误判断
括号匹配
1+(1+3*2
输出错误信息
输出错误信息
通
6
式子正误判断
计算符余
1++2*3+6
输出错误信息
输出错误信息
通
7
式子正误判断
含非计算符
x+y*z+w
输出错误信息
输出错误信息
通
8
式子正误判断
未输入
1+2*3
7
7
通
9
容错力
数0
2+30
输出数0
输出数0
通
10
容错力
动空格
1+ 2 * ( 3 + 4)
15
15
通
11
容错力
输#
2*(3+2)#
10
10
通
12
拓展功
位正数计算
10*(2+13)
150
输出错误信息
未通
13
拓展功
负数计算
4+3*(4)+5
3
输出错误信息
未通
15
拓展功
数计算
1+10*012
6
输出错误信息
未通
16
全体测试
终测试
2 *(4 –(3+3) )+3 #
1
1
通

Ø 部分运行截图
l 基计算操作
整运算(3)
括号运算(2)

l 式子正误判断

l 容错力

l 全体测试

七实验运行情况分析
Ø 优点
l 户输入格式较增添想容错系统户未输入户错输成#户字符间输入空格程序会智识出正确算数表达式计算正确答案
l 防错报错系统较完善方面考虑输入方面错误括号匹配计算符少输输输入非计算符等方面均考虑提示户错误信息便户检查输入状况
l 存储方式较规范采单链表存储户输入算术表达式更加清晰简单头结点存储表达式中符号数方便必时候统计终结果正确性
Ø 缺点
l 实现数字间四运算实现算数功方开方等
l 仅仅局限位数间运算法运算两位数两位数字运算
l 计算数字09整数法负数者数进行计算
l 法中遇法结果保留整数部分造成终结果预期结果存误差
l 控制台系统限制户交互性较差界面太简单单调
Ø 感受
通次带括号算数表达式计算实验光复前学单链表相关知识加采巩固关栈相关操作实现题目求基功基础增加拓展容期两周实验中刚开始整理思路接里编写代码填写实验报告步步完成唯独惜知识掌握够全面导致实现基功法进行进步扩展完善致户输入运算式未预期结构较遗憾方面
附录(源程序代码)
*
*实验：带括号算数表达式求值
*实现：栈
*语言：C
*作者：马健
*
#include
#include
#include

#define STACK_SIZE_FIRST 100 栈初始空间
#define STACK_SIZE_INCREASE 20 栈增加空间

*算术表达式单链表*
struct Expression{
char sign
struct Expression *next
}

*操作符操作数栈*
typedef struct{
char *top
char *bottom
int stack_size 栈空间
}Stack

struct Expression *GetExp() 键盘读入表达式存入单链表

*栈相关操作函数*
int StackCreate(Stack *s) 初始化空栈函数
int PUSH(Stack *s char c) 入栈函数
int POP(Stack *s char c) 出栈函数
char GetTop(Stack *s) 取出栈顶元素

*计算相关操作函数*
int Calculate(struct Expression *exp) 带括号算数表达式计算函数
int Count(char num1 char sign char num2) 两数计算
int IsOpOrNum(char c) 判断字符运算符
char JudgeLevel(char c1 char c2) 判断两运算符优先级
void PrintResult(struct Expression *expint result) 印终结果
int IsExpresiion(struct Expression *exp) 判断否正确算术表达式



void main()
{
struct Expression *head
int Result 0 定义终计算结果
int temp 0 定义循环参数
char select
while(temp 0)
{
head GetExp() 创建算术表达式单链表
if(IsExpresiion(head) 0 || head NULL) 算术表达式错误重新输入
{
printf(算术表达式错误请认真检查重新输入)
getch()
system(cls)
}
else
{
Result Calculate(head) 计算算术表达式
PrintResult(headResult) 输出终计算结果
printf(否继续计算 (y) 否(n)＼n) 否继续
select getch()
if(select ＇n＇ || select ＇N＇)
temp 1
else
system(cls)
}
}
}

读入算术表达式存储链表
struct Expression *GetExp()
{
printf(＼t带括号算术表达式求值＼n)
printf(请输入需计算算数表达式(＇＇结尾)＼n)
char c
int number 0
struct Expression *head NULL*p1*p2*first NULL 定义指针变量
head (struct Expression *)malloc(sizeof(struct Expression))
while((c getchar()) ＇＼n＇)
{
if(c ＇ ＇) 出现空格动删
{
p1 (struct Expression *)malloc(sizeof(struct Expression))
if(c ＇＇)
c ＇#＇
p1>sign c
if(first NULL)
first p1
else
p2>next p1
p2 p1
number++
}
}
if(p2>sign ＇#＇) 未输入＇＇动补齐
{
p1 (struct Expression *)malloc(sizeof(struct Expression))
p1>sign ＇#＇
p2>next p1
p2 p1
number++
}
head>next first
head>sign number + ＇0＇ 头结点存储表达式中字符数
if(head>next NULL)
p2>next NULL
return head
}

创建空栈
int StackCreate(Stack *s)
{
s>bottom (char *)malloc(STACK_SIZE_FIRST * sizeof(char))
if (s>bottom NULL)
{
printf(栈初始化失败＼n)
exit(0)
}
else
{
s>top s>bottom
s>stack_size STACK_SIZE_FIRST
}
return 1
}

入栈
int PUSH(Stack *s char c)
{
if(s>top s>bottom > STACK_SIZE_FIRST)
{
s>bottom (char *)realloc(s>bottom(STACK_SIZE_FIRST+STACK_SIZE_INCREASE) * sizeof(char))
if(s>bottom NULL)
{
printf(增加栈空间失败＼n)
exit(0)
}
s>stack_size s>stack_size + STACK_SIZE_INCREASE
}
*(s>top) c 赋值需入栈元素
s>top ++ 栈顶指针移
return 1
}

出栈
int POP(Stack *s char c)
{
if(s>top s>bottom)
{
printf(栈空出栈失败＼n)
exit(0)
}
else
{
c *(s>top)
s>top

}
return 1
}

获取栈顶元素
char GetTop(Stack *s)
{
char c
if(s>top s>bottom)
printf(栈空法获取栈顶元素＼n)
else
{
c * (s>top 1)
}
return c
}

计算算术表达式
int Calculate(struct Expression *exp)
{
exp exp>next 取表达式开始
char OpSign ＇ ＇ 存储出栈操作符
char NumSign1＇ ＇NumSign2 ＇ ＇ 存储出栈数字符
char result 存储部分运算结果
char temp ＇ ＇ 接受出栈操作数
Stack s_operator s_number
StackCreate(&s_operator) 创建操作符栈
StackCreate(&s_number) 创建数字栈
PUSH(&s_operator＇#＇) 先操作栈底压入＇#＇
printf(＼n计算程＼n)
while(exp>sign ＇#＇ || GetTop(&s_operator) ＇#＇)
{
操作数存入操作数栈
if(IsOpOrNum(exp>sign) 0)
{

PUSH(&s_numberexp>sign)
exp exp>next
}
操作符存入操作符栈
else if(IsOpOrNum(exp>sign) 1)
{
OpSign GetTop(&s_operator) 获取栈顶元素
switch(JudgeLevel(OpSignexp>sign)) 较栈顶元素运算符优先级
{
case ＇<＇PUSH(&s_operatorexp>sign) exp exp>nextbreak
case ＇＇POP(&s_operatorOpSign) exp exp>next break
case ＇>＇
POP(&s_operatorOpSign)
NumSign1 GetTop(&s_number)
POP(&s_numbertemp)
NumSign2 GetTop(&s_number)
POP(&s_numbertemp)
result Count(NumSign2OpSignNumSign1)
PUSH(&s_numberresult)
break
default break
}
}


}
result GetTop(&s_number) 获取终计算结果
return result ＇0＇

}
判断两运算符优先级
char JudgeLevel(char c1 char c2)
{
switch(c1)
{
case ＇+＇ switch(c2){
case ＇*＇
case ＇＇
case ＇(＇ return ＇<＇ break
default return ＇>＇ break
}
break
case ＇＇ switch(c2){
case ＇*＇
case ＇＇
case ＇(＇ return ＇<＇ break
default return ＇>＇ break
}
break
case ＇*＇ switch(c2){
case ＇(＇ return ＇<＇ break
default return ＇>＇ break
}
break
case ＇＇ switch(c2){
case ＇(＇ return ＇<＇ break
default return ＇>＇ break
}
break
case ＇(＇ switch(c2){
case ＇)＇ return ＇＇ break
default return ＇<＇ break
}
break
case ＇)＇ switch(c2){
case ＇+＇ return ＇>＇ break
default return ＇>＇ break
}
break
case ＇#＇ switch(c2){
case ＇#＇ return ＇＇ break
default return ＇<＇ break
}
break
default return ＇<＇ break
}

}

计算符号运算
int Count(char num1 char sign char num2)
{
int a0b0
a num1 ＇0＇ 取数字字符值
b num2 ＇0＇
int result 0
switch(sign)
{
case ＇+＇result a+bbreak
case ＇＇result abbreak
case ＇*＇result a*bbreak
case ＇＇result abbreak
defaultbreak
}
printf(d c d d＼nasignbresult) 输出计算程
return result + ＇0＇


}

判断字符运算符数字符
int IsOpOrNum(char c)
{
switch(c)
{
case ＇+＇
case ＇＇
case ＇*＇
case ＇＇
case ＇(＇
case ＇)＇
case ＇#＇
return 1 操作符
break
case ＇0＇
case ＇1＇
case ＇2＇
case ＇3＇
case ＇4＇
case ＇5＇
case ＇6＇
case ＇7＇
case ＇8＇
case ＇9＇
return 0 操作数
break
default
return 1
break
}
}

输出终结果
void PrintResult(struct Expression *expint result)
{
printf(＼n终计算结果＼n)
exp exp>next
while(exp NULL)
{
if( exp>sign ＇#＇)
exp>sign ＇＇
printf( cexp>sign)
exp exp>next
}
printf( d＼nresult)
}

判断户输入算术表达式否正确
int IsExpresiion(struct Expression *exp)
{
int parameter 1 定义判断表达式正确否参数
int i0j0 左右括号数量
if(exp>sign ＇0＇ < 4) 判断表达式字符数否正确
parameter 0
exp exp>next

while((parameter 1) && (exp NULL))
{
switch(IsOpOrNum(exp>sign))
{
case 0 果数字必须操作符左括号
exp exp>next
if(IsOpOrNum(exp>sign) 1 || exp>sign ＇(＇)
parameter 0
break
case 1 果操作符分情况

switch(exp>sign)
{

case ＇)＇ 果右括号计算符
i++
exp exp>next
if(IsOpOrNum(exp>sign) 1)
parameter 0
if(IsOpOrNum(exp>sign) 1)
if(exp>sign ＇(＇)
{
printf(11111＼n)
parameter 0
}
break
case ＇+＇ 果计算符右括号数字
case ＇＇
case ＇*＇
exp exp>next
if(exp>sign ＇(＇)
parameter 1
else if(IsOpOrNum(exp>sign) 0)
parameter 1
else
parameter 0
break
case ＇＇
exp exp>next
if(exp>sign ＇(＇)
parameter 1
else if(IsOpOrNum(exp>sign) 0)
{
if(exp>sign ＇0＇) 数0
{
printf(数0＼n)
parameter 0
}
}
else
parameter 0

break
case ＇(＇ 左括号数字
j++
exp exp>next
if(IsOpOrNum(exp>sign) 0)
if(exp>sign ＇(＇)
parameter 0
break
case ＇#＇ 等号等号字符
if(exp>next NULL)
parameter 0
exp exp>next
break
}
break
case 1 果非计算符数字错误
parameter 0
break
}
}
if(i j)
parameter 0
return parameter
}


文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档