表达式求值除了用文法实现之外,还可以直接用栈,将中缀表达式转化为后缀表达式。然后再用求表达式的值就轻而易举了。
下面贴程序源码:(可能有点长,呵呵:)
main.cpp
#include"stack.cpp" #include"stack.h" #include<iostream> using namespace std; /* * 该函数有两个功能 * 1. 输入中缀表达式 * 2. 将中缀表达式转化为后缀表达式 * 形参为两个指针分别指向两个数组(一个储存数字,一个储存运算符) * 返回值是数字和运算符的总个数(若转化出错,返回-1) */ int change(double *Darra,char *Carra) { int num = 0; //记录式子中数字和运算符总数 char ch; //暂时存储,输入字符 double dou; //暂时存储,输入数字 Stack<char> mychar; //存储运算符 bool wchar = false; //是否有非法字符 cout<<"请输入表达式(为了方便可以带空格),并以'='号结束:\n"<<endl; while( cin>>ch, '='!=ch ) { switch(ch) { case '0': case '5': case '1': case '6': case '2': case '7': case '3': case '8': case '4': case '9': num++; cin.putback(ch); //如果是数字,扔回去,用double型数据装 cin>>dou; cout<<dou<<ends; //后缀表达式部分输出 Darra[num] = dou; break; case '+': case '-': case '*': case '/': while( (!mychar.Isempty()) && //栈非空 (mychar.Top()!='(') && //栈顶元素不是空括号 ( (mychar.Top()=='*') || (mychar.Top()=='/') || (ch == '+') || (ch == '-') ) ) //栈顶运算符优先级不低于输入的运算符 //满足以上三个条件,将栈中元素全部d出 { num++; cout<<mychar.Top()<<ends; //后缀表达式部分输出 Carra[num] = mychar.Top(); mychar.Pop(); } mychar.Push(ch); //若不满足,则将出入运算符压入栈中 break; case '(': /* * 尝试解决省略*的运算不成功 if('/* * 模板类(栈)的实现 */ #ifndef Stack_cpp #define Stack_cpp #include"Stack.h" template<class T> Stack<T>::Stack() { top = -1; } template<class T> bool Stack<T>::Isempty() // If the stack is empty, return true; otherwise return false. { if(-1 == top) { return true; } else { return false; } } template<class T> void Stack<T>::Pop() // Pop an element from the top of the stack { if(top == -1) { cout<<"d出栈出错..."<<endl; exit(0); } top--; } template<class T> void Stack<T>::Push(T ele) // Push this element into the stack. { if(top > S_size) { cout<<"栈溢出..."<<endl; exit(0); } top++; elem[top] = ele; } template<class T> T Stack<T>::Top() // Return the top element of the stack. { if(-1 == top) { cout<<"已至栈底..."<<endl; //exit(0); } return elem[top]; } template<class T> int Stack<T>::Size() //Return the number of the elements in the stack. { return top; } template<class T> // clear all the elements in the stack void Stack<T>::clear() { top = -1; } #endif' == Carra[num] && num != 0) { num++; cout<<'*'<<ends; Carra[num] = '*'; } */ mychar.Push('('); //遇到开括号压入栈 break; case ')': if(mychar.Isempty()) //判断括号是否匹配 { cout<<"\n\n有多余的')'..."<<endl; return -1; } while(!mychar.Isempty()) //遇到闭括号,将栈中元素d出 { if('(' == mychar.Top()) //直至遇到开括号 { mychar.Pop(); break; } else //如果栈为空,任然没有开括号,则执行d出 *** 作时,会出现错误,退出系统 { num++; cout<<mychar.Top()<<ends; //后缀表达式部分输出 Carra[num] = mychar.Top(); mychar.Pop(); } } break; case ' ': break; default: //检测非法字符 wchar = true; } } while(!mychar.Isempty()) //将栈中剩余运算符输出 { if('(' == mychar.Top()) //括号不匹配 { cout<<"\n\n有多余的'('..."<<endl; return -1; } num++; cout<<mychar.Top()<<ends; //后缀表达式部分输出 Carra[num] = mychar.Top(); mychar.Pop(); } if(0 == num) //没有任何表达式输入 { cout<<"\n\n您没有输入任何表达式..."<<endl; return -1; } if(wchar) { cout<<"(字串中有非法字符)"; } cout<<endl<<"\n以上为中缀表达式和相应的后缀表达式,"; return num; } /* * 运算函数,将储存在数组中的符号和数字(后缀表达式)取出,计算成结果返回 * 形参: 储存有后缀表达式的两个数组首地址(此处若用栈,则后缀表达式从栈中输出时,其顺序完全反相),后缀表达式的长度 * 返回值: 后缀表达式的计算结果 */ double Compute(char *Carra,double *Darra, int num) { int i = 1; //取后缀表达式的辅助变量 double d1,d2; //暂存栈中d出的两个变量 Stack<double> Res; //运算栈,储存数字 while( i <= num ) { if(Carra[i] == '/* * 模板类(栈) */ #ifndef Stack_h #define Stack_h #define S_size 50 //the size of the stack template<class T> class Stack { public: Stack(); void Pop(); // Pop an element from the top of the stack void Push(T elem); // Push this element into the stack. T Top(); // Return the top element of the stack. bool Isempty(); // If the stack is empty, return true; otherwise return false. int Size(); // Return the number of the elements in the stack. void clear(); // clear all the elements in the stack private: T elem[S_size]; int top; }; #endif') //如果i处是无效运算符,说明后缀表达式中,i处对应的应该是数字 { Res.Push(Darra[i]); //数字入栈 } else //如果是运算符 { d1 = Res.Top(); Res.Pop(); d2 = Res.Top(); Res.Pop(); //从栈顶d出两个数据进行计算 switch(Carra[i]) { case '+': Res.Push(d1+d2); //计算后压回栈 break; case '-': Res.Push(d2-d1); break; case '*': Res.Push(d1*d2); break; case '/': if(0 == d1) { cout<<"请注意分母不能为零..."<<endl; system("pause"); exit(0); } Res.Push(d2/d1); break; default: cout<<"(Compute)运算符匹配出错了..."<<endl; exit(0); } } i++; } return Res.Top(); //d出栈中最后一个数字(计算结果) } int main() { int i; double Darra[S_size]; //装入数据 char Carra[S_size]; //装入运算符 for(i=0; i<S_size; i++) //将储存运算符的数组做一个标记,以明确该下标所对应的是数字还是运算符 Carra[i] = ''; //若检测到Carra[i] = '',则说明Carra[i]中没有存入运算符,而Darra[i]中存储了一个数字 cout<<"************************* 一个简单表达式计算程序 *************************"<<endl; cout<<" ——by HQ"<<endl; cout<<"注意:请写全表达式,不要省略'*',写负数时请写成 '0 - x'的形式.\n"<<endl; if( ( i = change(Darra,Carra) )== -1 ) //判断转换是否成功 { cout<<"\n转换失败..."<<endl; system("pause"); exit(0); } else { cout<<"其计算结果为:\n"<<endl; cout<<Compute(Carra,Darra,i)<<endl; //计算并输出结果 } system("pause"); return 0; }
stack.cpp
stack.h
运行结果:
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)