用栈实现表达式求值

1、/ / /实验一：表达式求值 /文件名:stack.h /文件功能：程序中栈的实现，这里是用链式存储 /时间:2009年4月10日 / #ifndef STACK_H_INCLUDED #define STACK_H_INCLUDED #include #include #include #include #include using namespace std; #define SIZE 100 template struct node ElemType elem; node *next; ; / / /定义栈 / template class stack private: node *to

2、p; /头结点 public: / / /使用构造函数初始化 / stack() top = new node; top-next = NULL; top-elem = 0; / / /使用析构函数销栈 / stack() node *p = this-top; while (p-next != NULL) top = p-next; delete p; p = top; delete p; / / /压栈 / void push(ElemType e) node *p; p = new node; p-elem = e; p-next = this-top-next; this-top-ne

3、xt = p; / / /出栈 / void pop(ElemType &e) node *p; if(!IsEmpty() e = this-top-next-elem; p = this-top-next; this-top-next = p-next; delete p; / / /得到栈顶元素 / void GetTop(ElemType &e) e = this-top-next-elem; / / /判断栈是否为空 / bool IsEmpty(void) if (this-top-next = NULL) return true; else return false; ; #en

4、dif / STACK_H_INCLUDED /stack.h文件结束 / / /实验一：表达式求值 /文件名:ExpEvaluate.h /文件功能：实现表达式的中缀转换成后缀，并且计算出结果 /时间:2009年4月10日 / #ifndef EXPEVALUATE_H_INCLUDED #define EXPEVALUATE_H_INCLUDED #include stack.h class expr private: char ExpSIZE; char PostExpSIZE; double _value; public: expr() _value = 0; for (int i=0

5、; iSIZE; i+) Expi = 0; PostExpi= 0; void init(void) for (int i=0; iSIZE; i+) Expi = 0; PostExpi= 0; / / /得到该表达式计算后的结果 / double GetValue(void) return _value; / / /判断用户输入的表达式是否为合法的 / bool IsLegal(char *a) char tempSIZE; char test; int length = strlen(a); int left=0,right=0; int isnumber=0, ischar=0; i

6、f(length = 0) cout输入为空，请输入表达式！endl; return false; for(int i=0; iSIZE; i+) tempi = 0; / /过滤掉空格 for(int i=0,k=0; ilength; i+,k+) test = ai; if(test = ) k-; continue; tempi = test; strcpy(a,temp); length = strlen(a); / /长度不合法 for(int i=0; i SIZE) cout存储空间不够！endl; exit(0); / /处理数字与括号间省略括号的情况 for(int j=0

7、,k=0; j=0 & aj-1=9) | aj-1 = ) tempk = *; /添上省略的括号 tempk+1 = test; k+; continue; tempk = test; strcpy(a,temp); length = strlen(a); for(int i=0; iSIZE; i+) tempi = 0; / /处理负数问题 for(int j=0,k=0; jlength; j+,k+) test = aj; if(j=0 & test = -) tempk = 0; /第一个数是负数的时候，在最前面加一个负号 tempk+=-; continue; if(test

8、= ( & aj+1 = -) tempk = (; /遇到加括号的负数时，在括号和负号之间添上一个0 tempk+1 = 0; tempk+2 = -; k+=2; j+; continue; tempk = test; strcpy(a,temp); length = strlen(a); / /判断有没有非法的字符 for(int m=0; mlength; m+) test = am; if(!(test=+|test=-|test=*|test=/|test=|test=(|test=)|(test=0)|test=.) cout含有非法的字符！endl; return false;

9、 / / /检测括号是否匹配 for(int m=0; mlength; m+) test = am; if(test = () left+; if(test = ) right+; if(left != right) cout括号不匹配！endl; return false; / /判断表达式的一些数字与符号的错误 for(int p=0; plength; p+) test = ap; / /判断小数的非法 if(test=.) if(p=0 | p=length-1) cout小数点有错误！9 & ap+19 & ap-10) cout小数点有错误！endl; return false;

10、 / /判断运算符和数字的数量是否合法 if(test=0) | test=.) while(test=0 | test= .) test = a+p; isnumber+; p-; continue; if(test=+|test=-|test=*|test=/|test=) ischar+; continue; /符号数量少 if(isnumber ischar+1) cout缺少符号！endl; return false; /数字数量少 if(isnumber ischar+1) cout缺少数字！endl; return false; return true; / / /使用提供的字符

11、串来设置表达式前缀的值 / bool SetExp(char* a) if (IsLegal(a) strcpy(Exp, a); return true; else cout输入的表达式不合法！请重新输入！endl; return false; / / /将表达式前缀转换为后缀，这里优先级已经体现在程序中，没有另外建立判断函数 / void translate(void) stack oprate; char temp = *Exp; char Top; char elem; int j=0; for (int i=0; temp != 0; i+) temp = *(Exp+i); swi

12、tch (temp) case (: /遇左括号进栈 oprate.push(temp); break; case ): if (!oprate.IsEmpty() /遇右括号一直出栈直到栈顶为左括号，并且将左括号删除 oprate.GetTop(Top); while (Top != () oprate.pop(elem); PostExpj+ = elem; if (!oprate.IsEmpty() oprate.GetTop(Top); else break; oprate.pop(elem); break; case +: case -: /遇加减号优先级相同，可以一同处理 if (

13、!oprate.IsEmpty() oprate.GetTop(Top); while (Top != () oprate.pop(elem); PostExpj+ = elem; if (!oprate.IsEmpty() oprate.GetTop(Top); else break; oprate.push(temp); break; case : if (!oprate.IsEmpty() oprate.GetTop(Top); while (Top=) /优先级最高 oprate.pop(elem); PostExpj+ = elem; if (!oprate.IsEmpty() op

14、rate.GetTop(Top); else break; oprate.push(temp); break; case *: case /: /乘除法优先级也是相同的 if (!oprate.IsEmpty() oprate.GetTop(Top); while (Top=* | Top=/ | Top=) oprate.pop(elem); PostExpj+ = elem; if (!oprate.IsEmpty() oprate.GetTop(Top); else break; oprate.push(temp); break; case : /过滤空格 break; default:

15、 /处理数字，并以#号作为数字结束符号 while (temp=0 & temp=9) | temp=.) PostExpj+ = temp; i+; temp = *(Exp+i); i-; PostExpj+ = #; break; while (!oprate.IsEmpty() oprate.pop(elem); PostExpj+ = elem; PostExpj = 0; / / /计算后缀表达式的值 / bool ComputeValue(void) stack number; char temp = *PostExp; /用来暂存字符 double one=0, two=0,

16、value=0; /运算的数和结果 double date = 0, ispoint = 0; int count=0; int length = strlen(PostExp); /后缀表达式的长度 for (int i=0; ilength; i+) temp = *(PostExp+i); switch (temp) case +: /遇到加号将数字出栈，进行运算 one = 0; two = 0; value = 0; number.pop(one); number.pop(two); value = one + two; number.push(value); break; case

17、 -: /遇到号将数字出栈，进行运算 one = 0; two = 0; value = 0; number.pop(one); number.pop(two); value = two - one; number.push(value); break; case *: /计算乘号 one = 0; two = 0; value = 0; number.pop(one); number.pop(two); value = two * one; number.push(value); break; case /: /计算除号 one = 0; two = 0; value = 0; number

18、.pop(one); number.pop(two); if (one != 0) value = two / one; else cout除零错误！退出 0) value = pow(two, one); else cout错误！退出=0 & temp =9) | temp=.) if(temp = .) /遇到小数点然后后面的数字计算方式会改变 ispoint = 1; i+; temp = *(PostExp+i); continue; if (ispoint=0) date=date*10+temp-0; else count+; date += (temp-0)*pow(0.1,count); i+; temp = *(PostExp+i); i-; number.push(date); number.pop(_value); return true; / / / /将表达式的中缀式和后缀式以及最终的结果打印输出 / void Display(v