数据结构基于栈的算术表达式求值算法

/****************************************************************/ /* Creator: YM ([email protected]) */ /* For: 数字媒体11-1,2 */ /* Date: 2012.11.16 */ /* All copyrights reserved ! */ /****************************************************************/ #include"stack.h" //自己定义的栈的头文件 #include <iostream> #include <conio.h> //程序中使用了getche和getch using namespace::std; Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base = new SElemType[STACK_INIT_SIZE]; if( !S.base ) { cout<<"存储分配失败."<<endl; exit(OVERFLOW); /* 存储分配失败 */ } S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } Status GetTop(SqStack &S, SElemType &e) { /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */ if(S.top == S.base) { return ERROR; } e = *(S.top-1); return OK; } Status Push(SqStack &S, SElemType e) { /* 插入元素e为新的栈顶元素 */ if(S.top-S.base == S.stacksize){ /* 栈满 */ cout<<"栈满，无法压栈!"<<endl; return ERROR; } *S.top++ = e; return OK; } Status Pop(SqStack &S, char &e) { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(S.top == S.base) return ERROR; e = *--S.top; return OK; } Status Clear(SqStack &S) { char e; while(S.base != S.top) { Pop(S, e); } return OK; } Status Destroy(SqStack &S) { if(S.base != S.top) { delete []S.base; S.base = S.top = NULL; } return OK; } TYPE_Status In(char c) { /* 判断c是否为运算符 */ switch(c) { //input an operator case '+': case '-': case '*': case '/': case '(': case ')': return TYPE_OPTR; //input an operand case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': return TYPE_OPND; //input an end case '#': return TYPE_END; //other case default: return TYPE_ERROR; } } char Precede(char t1, char t2) { /* 根据教科书表3.1，判断两符号的优先关系 */ char f; //switch(t2) //{ //case '+': //case '-':if(t1=='(' || t1=='#') // f='<'; // else // f='>'; // break; // //......补充完整 //} switch(t1) { // case + or - case '+': case '-':if(t2=='*' || t2=='/' || t2=='(') f='<'; else f='>'; break; // case * or / case '*': case '/':if(t2=='(') f='<'; else f='>'; break; // case ( case '(':if(t2!='#') { if(t2==')') f='='; else f='<'; } else f='E';// error break; // case ) case ')':if(t2!='(') { //if(t2=='+' || t2=='-' || t2=='*' || t2=='/' || t2==')' || t2=='#') f='>'; } else f='E';// error break; // case # case '#':if(t2!=')') { if(t2=='#') f='='; else f='<'; } else f='E';// error break; } return f; } char Operate(char a, char theta, char b) //进行运算的函数 { char c; a = a - 48; b = b - 48; switch(theta) { case '+': c = a+b+48; break; case '-': c = a-b+48; break; case '*': c = a*b+48; break; case '/': c = a/b+48; break; //......补充完整 } return c; } char EvaluateExpression(SqStack S_OPND) { /* 算术表达式求值的算符优先算法。设 OPTR 和 OPND 分别为运算符栈和运算数栈 */ //......补充完整 char e; GetTop(S_OPND, e); return e; } int GetCharLen(char c_input[]) { int count = 0; while(c_input[count]!='\0') { count++; } return count; } void main() { TYPE_Status t_CurChar; int len; char c_input[MAX_CHAR_LEN]; bool b_Flag = true, b_Flag2 = true; char exitFlag; SqStack S_OPND, S_OPTR; // initialize OPRT stack & OPND stack. InitStack(S_OPTR); InitStack(S_OPND); while(1) { // initialize OPRT stack & OPND stack. //InitStack(S_OPTR);Push(S_OPTR,'#'); //InitStack(S_OPND); Clear(S_OPND); Clear(S_OPTR); Push(S_OPTR,'#'); cout<<"******************************************************************"<<endl; cout<<"** 数媒11-1,2 YM **"<<endl; cout<<"** 2012.11.16 **"<<endl; cout<<"******************************************************************"<<endl; cout<<"1. 请输入算术表达式,并以#结束,中间计算过程要是个位数:"<<endl; cout<<"----------------------------------"<<endl; cin>> c_input; len = GetCharLen(c_input); cout<<"----------------------------------"<<endl; cout<<"2. 您输入的算术表达式为："<< c_input <<"\t"; cout<<"长度为："<< len <<endl; if(c_input[len-1]!='#') { cout<<"----------------------------------"<<endl; cout<<"% Warning：算术表达式应以“#”结尾！"<<endl; cout<<"----------------------------------"<<endl; cout<<endl<<endl; } else { b_Flag = true; b_Flag2 = true; for(int i=0; i<len && b_Flag && b_Flag2; /*i++*/) { char ch = c_input[i]; char eChar, eChar2; GetTop(S_OPTR, eChar); if(ch!='#' || eChar!='#') { t_CurChar = In(ch); switch(t_CurChar) { case TYPE_OPND: Push(S_OPND, ch); i++; //cout<<"输入了一个操作数."<<endl; break; case TYPE_OPTR: //cout<<"输入了一个操作符."<<endl; //break; case TYPE_END: { //cout<<"输入了一个结束符."<<endl; GetTop(S_OPTR, eChar2); switch(Precede(eChar2,ch)) { case '<': Push(S_OPTR, ch); i++; //? break; case '>': char theta; char a, b; Pop(S_OPTR, theta); Pop(S_OPND, b); Pop(S_OPND, a); Push(S_OPND, Operate(a, theta, b));//i++; break; case '=': char x; Pop(S_OPTR, x); i++; break; } break; } default://case TYPE_ERROR: cout<<"% Warning: 输入表达式中有非法字符，请输入正确表达式."<<endl; b_Flag = false; //clear stacks of OPND & OPRT Clear(S_OPND); Clear(S_OPTR); break; } } else { b_Flag2 = false; } } if(b_Flag) { char n; n = EvaluateExpression(S_OPND); cout<<"----------------------------------"<<endl; cout<<"3. 计算结果为："<<n<<endl; cout<<"----------------------------------"<<endl; } // exit program or not bool b_exitFlag = true; while(b_exitFlag) { cout<<endl<<"请问您是否继续程序？(N (exit) or Y (continue))"<<endl; //char exitFlag; //cin>>exitFlag; exitFlag = getche(); //while(GetCharLen(&exitFlag)>1) //{ // cout<<"Only one character is permitted to be input!"<<endl; // cin>>exitFlag; //} if(exitFlag == 'N' || exitFlag == 'n') { // b_exitFlag = true; // useless exit(0); } else { if(exitFlag == 'Y' || exitFlag == 'y') { b_exitFlag = false; Clear(S_OPND); Clear(S_OPTR); } else { cout<<endl<<endl; cout<<"----------------------------------"<<endl; cout<<"% Warning：Please input \"Y\" or \"N\"!"<<endl; cout<<"----------------------------------"; } } } } cout<<endl<<endl; } }