二 课程设计2——算术表达式求值
一、需求分析
二、程序的主要功能
三、程序运行平台
四、数据结构
五、算法及时间复杂度
六、测试用例
七、程序源代码
三 感想体会与总结
算术表达式求值
页脚内容
一、需求分析
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。
二、程序的主要功能
（1） 从键盘读入一个合法的算术表达式，输出正确的结果。
（2） 显示输入序列和栈的变化过程。
三、程序运行平台
Visual C++ 6.0版本
四、数据结构
本程序的数据结构为栈。
（1）运算符栈部分：
struct SqStack //定义栈
页脚内容
{
char *base; //栈底指针
char *top; //栈顶指针
int stacksize; //栈的长度
};
int InitStack (SqStack &s) //建立一个空栈S
{
if (!(s.base = (char *)malloc(50 * sizeof(char))))
exit(0);
s.top=s.base;
s.stacksize=50;
return OK;
页脚内容
}
char GetTop(SqStack s,char &e) //运算符取栈顶元素
{
if (s.top==s.base) //栈为空的时候返回ERROR
{
printf(\"运算符栈为空!\\n\");
return ERROR;
}
else
e=*(s.top-1); //栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK
return OK;
页脚内容
}
int Push(SqStack &s,char e) //运算符入栈
{
if (s.top-s.base >= s.stacksize)
{
printf(\"运算符栈满!\\n\");
s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); 个存储空间
if(!s.base) exit (OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=5;
页脚内容
//栈满的时候，追加5
}
*(s.top)++=e; //把e入栈
return OK;
}
int Pop(SqStack &s,char &e) //运算符出栈
{
if (s.top==s.base) //栈为空栈的时候，返回ERROR
{
printf(\"运算符栈为空!\\n\");
return ERROR;
}
else
页脚内容
{
e=*--s.top; //栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OK
return OK;
}
}
int StackTraverse(SqStack &s) //运算符栈的遍历
{
char *t;
t=s.base ;
if (s.top==s.base)
{
printf(\"运算符栈为空!\\n\"); //栈为空栈的时候返回ERROR
页脚内容
return ERROR;
}
while(t!=s.top)
{
printf(\" %c\栈不为空的时候依次取出栈内元素
t++;
}
return ERROR;
}
（）数字栈部分：
struct SqStackn //定义数栈
{
页脚内容
int *base; //栈底指针
int *top; //栈顶指针
int stacksize; //栈的长度
};
int InitStackn (SqStackn &s) //建立一个空栈S
{
s.base=(int*)malloc(50*sizeof(int));
if(!s.base)exit(OVERFLOW); //存储分配失败
s.top=s.base;
s.stacksize=50;
return OK;
}
页脚内容
int GetTopn(SqStackn s,int &e) //数栈取栈顶元素
{
if (s.top==s.base)
{
printf(\"运算数栈为空!\\n\"); //栈为空的时候返回ERROR
return ERROR;
}
else
e=*(s.top-1); //栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OK
return OK;
}
页脚内容
int Pushn(SqStackn &s,int e) //数栈入栈
{
if (s.top-s.base >=s.stacksize)
{
printf(\"运算数栈满!\\n\"); //栈满的时候，追加5个存储空间
s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) );
if(!s.base) exit (OVERFLOW);
s.top=s.base+s.stacksize; //插入元素e为新的栈顶元素
s.stacksize+=5;
}
*(s.top)++=e; //栈顶指针变化
页脚内容
return OK;
}
int Popn(SqStackn &s,int &e) //数栈出栈
{
if (s.top==s.base)
{
printf(\" 运算符栈为空!\\n\"); //栈为空栈的视时候，返回ERROR
return ERROR;
}
else
{
e=*--s.top; //栈不空的时候，则删除S的栈顶元素，用e返回其值，并返回OK
页脚内容
return OK;
}
}
int StackTraversen(SqStackn &s) //数栈遍历
{
int *t;
t=s.base ;
if (s.top==s.base)
{
printf(\" 运算数栈为空!\\n\"); //栈为空栈的时候返回ERROR
return ERROR;
}
页脚内容
while(t!=s.top)
{
printf(\" %d\栈不为空的时候依次输出
t++;
}
return ERROR;
}
五、算法及时间复杂度
1、算法：
建立两个不同类型的空栈，先把一个‘# ’压入运算符栈。输入一个算术表达式的字符串（以‘#’结束），从第一个字符依次向后读，把读取的数字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算符栈顶得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后两个‘#’遇到一起则运算结束。数字栈顶的数字就是要求的结果。
页脚内容
2、时间复杂度：O(n)
数据压缩存储栈，其操作主要有：
建立栈int Push(SeqStack *S, char x)
入栈int Pop(SeqStack *S, char x)
出栈。
以上各操作运算的平均时间复杂度为O(n)，其主要时间是耗费在输入操作。
六、测试用例
如图所示。
页脚内容
最终结果如图所示：
七、源代码
/**************************************************************************************************
第七题 算术表达式求值
页脚内容
[问题描述]
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，
运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，
如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。
编程利用“算符优先法”求算术表达式的值。
[基本要求]
（1） 从键盘读入一个合法的算术表达式，输出正确的结果。
（2） 显示输入序列和栈的变化过程。
***************************************************************************************************/
#include #include 页脚内容 #include #include #include #include #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 //#define STACKINCREMENT 10 //======================================================== // 以下定义两种栈，分别存放运算符和数字 //======================================================== 页脚内容 //*******************运算符栈部分************************* struct SqStack //定义栈 { char *base; //栈底指针 char *top; //栈顶指针 int stacksize; //栈的长度 }; int InitStack (SqStack &s) //建立一个空栈S { if (!(s.base = (char *)malloc(50 * sizeof(char)))) exit(0); s.top=s.base; 页脚内容 s.stacksize=50; return OK; } char GetTop(SqStack s,char &e) //运算符取栈顶元素 { if (s.top==s.base) //栈为空的时候返回ERROR { printf(\"运算符栈为空!\\n\"); return ERROR; } else 页脚内容 e=*(s.top-1); //栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK return OK; } int Push(SqStack &s,char e) //运算符入栈 { if (s.top-s.base >= s.stacksize) { printf(\"运算符栈满!\\n\"); s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); 个存储空间 if(!s.base) exit (OVERFLOW); 页脚内容 //栈满的时候，追加5 s.top=s.base+s.stacksize; s.stacksize+=5; } *(s.top)++=e; //把e入栈 return OK; } int Pop(SqStack &s,char &e) //运算符出栈 { if (s.top==s.base) //栈为空栈的时候，返回ERROR { printf(\"运算符栈为空!\\n\"); return ERROR; 页脚内容 } else { e=*--s.top; //栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OK return OK; } } int StackTraverse(SqStack &s) //运算符栈的遍历 { char *t; t=s.base ; if (s.top==s.base) 页脚内容 { printf(\"运算符栈为空!\\n\"); //栈为空栈的时候返回ERROR return ERROR; } while(t!=s.top) { printf(\" %c\栈不为空的时候依次取出栈内元素 t++; } return ERROR; } //**********************数字栈部分*************************** 页脚内容 struct SqStackn //定义数栈 { int *base; //栈底指针 int *top; //栈顶指针 int stacksize; //栈的长度 }; int InitStackn (SqStackn &s) //建立一个空栈S { s.base=(int*)malloc(50*sizeof(int)); if(!s.base)exit(OVERFLOW); //存储分配失败 s.top=s.base; s.stacksize=50; 页脚内容 return OK; } int GetTopn(SqStackn s,int &e) //数栈取栈顶元素 { if (s.top==s.base) { printf(\"运算数栈为空!\\n\"); //栈为空的时候返回ERROR return ERROR; } else e=*(s.top-1); //栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OK 页脚内容 return OK; } int Pushn(SqStackn &s,int e) //数栈入栈 { if (s.top-s.base >=s.stacksize) { printf(\"运算数栈满!\\n\"); //栈满的时候，追加5个存储空间 s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) ); if(!s.base) exit (OVERFLOW); s.top=s.base+s.stacksize; //插入元素e为新的栈顶元素 s.stacksize+=5; 页脚内容 } *(s.top)++=e; //栈顶指针变化 return OK; } int Popn(SqStackn &s,int &e) //数栈出栈 { if (s.top==s.base) { printf(\" 运算符栈为空!\\n\"); //栈为空栈的视时候，返回ERROR return ERROR; } else 页脚内容 { e=*--s.top; //栈不空的时候，则删除S的栈顶元素，用e返回其值，并返回OK return OK; } } int StackTraversen(SqStackn &s) //数栈遍历 { int *t; t=s.base ; if (s.top==s.base) { printf(\" 运算数栈为空!\\n\"); //栈为空栈的时候返回ERROR 页脚内容 return ERROR; } while(t!=s.top) { printf(\" %d\栈不为空的时候依次输出 t++; } return ERROR; } //======================================================== // 以下定义函数 //================================================== 页脚内容 ====== int Isoperator(char ch) //判断是否为运算符，分别将运算符和数字进入不同的栈 { switch (ch) { case '+': case '-': case '*': case '/': case '(': case ')': case '#': 页脚内容 return 1; default: return 0; } } int Operate(int a, char op, int b) //运算操作 { int result; switch(op) { case '+': result=a+b; 页脚内容 break; case '-': result=a-b; break; case '*': result=a*b; break; case '/': result=a/b; break; } return result; 页脚内容 } char Precede(char ch1, char ch2) //运算符优先级的比较 { char p; switch(ch1) { case '+': case '-': if (ch2=='+'||ch2=='-'||ch2==')'||ch2=='#') p = '>'; //ch1运算符的优先级小于ch2运算符 else p = '<'; 页脚内容 break; case '*': case '/': if (ch2 == '(') p = '<'; else p = '>'; break; case '(': if (ch2 == ')') p = '='; else if (ch2 == '#') 页脚内容 { printf(\" 表达式错误!运算符不匹配!\\n\") ; exit(0); } else p = '<'; break ; case ')': if (ch2 == '(') { printf(\" 表达式错误!运算符不匹配!\\n\") ; exit(0); 页脚内容 } else p = '>'; break ; case '#': if (ch2 == ')') { printf(\" 表达式错误!运算符不匹配!\\n\") ; exit(0); } else if (ch2 == '#') p = '='; 页脚内容 else p='<'; break; } return p; } //======================================================== // 以下是求值过程 //======================================================== int EvaluateExpression() //参考书p53算法3.4 { 页脚内容 int a, b, temp, answer; char ch,op,e; char *str; int j = 0; SqStackn OPND; //OPND为运算数字栈 SqStack OPTR; //OPTR为运算符栈 InitStack(OPTR); Push(OPTR,'#'); //,所以此栈底是'#'，因为运算符栈以'#'作为结束标志 InitStackn(OPND); // printf(\"\\n\\n按任意键开始求解:\\n\\n\"); // ch=getch(); printf(\"\\n请输入表达式并以'#'结束:\\n\"); 页脚内容 str =(char*)malloc(50*sizeof(char)); gets(str); ch=str[j]; //ch是字符型的，而e是整型的整数 j++; GetTop(OPTR,e); //e为栈顶元素返回值 while (ch!='#' || e!='#') { if (!Isoperator(ch)) //遇到数字,转换成十进制并计算 { temp=ch-'0'; //将字符转换为十进制数 ch=str[j]; j++; 页脚内容 while(!Isoperator(ch)) { temp=temp*10 + ch-'0'; //将逐个读入运算数的各位转化为十进制数 ch=str[j]; j++; } Pushn(OPND,temp); } else if (Isoperator(ch)) switch (Precede(e,ch)) //判断是否是运算符,不是运算符则进栈 页脚内容 { case '<' : Push(OPTR,ch); // 栈顶元素优先权低 ch = str[j++]; printf(\"\\n\\n 运算符栈为：\\n\"); //输出栈，显示栈的变化 StackTraverse(OPTR); printf(\"\\n 运算数栈为：\\n\"); StackTraversen(OPND); break; case '=' : Pop(OPTR,op); // 脱括号并接收下一字符 ch = str[j++] ; printf(\"\\n\\n 运算符栈为：\\n\"); StackTraverse(OPTR); 页脚内容 printf(\"\\n 数栈为：\\n\"); StackTraversen(OPND); break; case '>' : Pop(OPTR,op); //弹出最上面两个，并运算，把结果进栈 Popn(OPND,b); Popn(OPND,a); Pushn(OPND,Operate(a,op,b)); printf(\"\\n\\n 运算符栈为：\\n\"); StackTraverse(OPTR); printf(\"\\n 数栈为：\\n\"); StackTraversen(OPND); } 页脚内容 else { printf(\"您的输入有问题，请检查重新输入!\"); exit(0); } GetTop(OPTR,e); //取出运算符栈最上面元素是否是'#' } //while GetTopn(OPND,answer); //已输出。数字栈最上面即是最终结果 return answer; } //======================================================== // 执行部分 页脚内容 //======================================================== void ShowMenu() { printf(\"\\n\\n\"); printf(\"███████████████████████████████████████\\n\"); printf(\"██ ██\\n\"); printf(\"██ 表达式求值系统 ██\\n\"); printf(\"██ ██\\n\"); printf(\"███████████████████████████████████████\\n\"); } 页脚内容 void Quit(); void Manage() { int answer; // ShowMenu(); answer=EvaluateExpression(); printf(\"\\n\\n表达式结果是: %d\\n\ Quit(); } void Quit() { char ch; 页脚内容 printf(\" 本次运算结束。\\n\"); printf(\" 继续本系统吗？\\n\\n\"); printf(\" 继续运算请按Y/y \"); printf(\"\\n 退出程序请按N/n \"); printf(\" \\n___________________________________________________________________\\n\"); ch=getch(); ch=toupper(ch); //将ch字符转换成大写字母 if(ch == 'N') { printf(\"\\n\\n 系统退出。\\n\"); exit(0); } 页脚内容 Manage(); } int main() { ShowMenu(); Manage(); return 0; } 感想体会与总结 好的算法＋编程技巧＋高效率＝好的程序。 、做什么都需要耐心，做设计写程序更需要耐心。一开始的时候，我写函数写的很快，可是等最后调试的时候发现错误很隐蔽，就很费时间了。后来我先在纸上构思出函数的功能和参数，考虑好接口之后才动手编，这样就比较容易成功了。 页脚内容 、做任何事情我决定都应该有个总体规划。之后的工作按照规划逐步展开完成。对于一个完整的程序设计，首先需要总体规划写程序的步骤，分块写分函数写，然后写完一部分马上纠错调试。而不是像我第一个程序，一口气写完，然后再花几倍的时间调试。一步步来，走好一步再走下一步。写程序是这样，做项目是这样，过我们的生活更是应该这样。 、感觉一开始设计结构写函数体现的是数据结构的思想，后面的调试则更加体现了人的综合素质，专业知识、坚定耐心、锲而不舍，真的缺一不可啊。 、通过这次课设，不仅仅复习了C语言相关知识、巩固了数据结构关于栈和排序的算法等知识，更磨练了我的意志。 页脚内容 因篇幅问题不能全部显示，请点此查看更多更全内容