数据结构课程设计----表达式求值
|
表达式求值问题 ? ? ? ? 给定一个四则运算的中缀表达式，编程计算表达式的值。 基本要求： ? ? （1）在给定的表达式中要包含括号； ? ? （2）栈的操作要求自己完成，不允许调用类库中的方法； ? ? （3）对不同的操作编写相应的函数。 测试数据要求： ? ? ? ? 给定测表达式（字符串）中的数字字符要有包含两位以上的数字字符。 /*********************************************************************************************** *** 第七题 算术表达式求值 [问题描述 ] 一个算术表达式是由操作数 (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) ); //栈满的时候，追加 5 个存储空间 if(!s.base) exit (OVERFLOW); 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); // 栈不为空的时候依次取出栈内元素 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); // 栈不为空的时候依次输出 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("nn 按任意键开始求解 :nn"); // 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("nn 运算符栈为： n"); //输出栈，显示栈的变化 StackTraverse(OPTR); printf("n 运算数栈为： n"); StackTraversen(OPND); break; case '=' : Pop(OPTR,op); // 脱括号并接收下一字符 ch = str[j++] ; printf("nn 运算符栈为： n"); StackTraverse(OPTR); printf("n 数栈为： n"); StackTraversen(OPND); break; case '>' : Pop(OPTR,op); //弹出最上面两个，并运算，把结果进栈 Popn(OPND,b); Popn(OPND,a); Pushn(OPND,Operate(a,b)); printf("nn 运算符栈为： n"); StackTraverse(OPTR); printf("n 数栈为： n"); StackTraversen(OPND); } else { printf(" 您的输入有问题，请检查重新输入 !"); exit(0); } GetTop(OPTR,e); //取出运算符栈最上面元素是否是 '#' } //while GetTopn(OPND,answer); //已输出。数字栈最上面即是最终结果 return answer; } //======================================================== // 执行部分 //======================================================== void ShowMenu() { printf("nn"); printf(" 表达式求值系统 n"); } void Quit(); void Manage() { int answer; // ShowMenu(); answer=EvaluateExpression(); printf("nn 表达式结果是 : %dn",answer); Quit(); } void Quit() { char ch; printf(" 本次运算结束。 n"); printf(" 继续本系统吗？ nn"); printf(" 继续运算请按 Y/y "); printf("n 退出程序请按 N/n "); printf("n___________________________________________________________________n"); ch=getch(); ch=toupper(ch); //将 ch 字符转换成大写字母 if(ch == 'N') { printf("nn 系统退出。 n"); exit(0); } Manage(); } int main() { ShowMenu(); Manage(); return 0; } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |