大家好!今天带来的是自己实现的用C++实现的10以内整数的科学计算器,其中涉及中缀表达式到后缀表达式(逆波兰表示法),后缀表达式的求值,涉及栈这一数据结构的压栈,弹栈,存取栈顶元素和判断栈是否为空等操作.

计算器在生活中应用广泛.众所周知,我们往计算器中输入的是由数字,运算符组成的表达式,这个表达式被称为中缀表达式,因其运算符写在数的中间,如(1+2)*3.而用栈实现的计算器所处理的是后缀表达式,即运算符在数字的后面,这涉及到中缀表达式转后缀表达式的算法.如(1+2)*3的后缀表达式是12+3*.后缀表达式也成为逆波兰表示法,因其是一种由波兰数学家扬·武卡谢维奇在1920年引入的数学表达式方式.

整个工程涉及两个编译单元,即main.cpp主函数文件和caculatefuncs.h自定义头文件.main.cpp的代码十分简单,就是读入中缀表达式,然后调用toPostFix函数,转变为后缀表达式,再调用toDouble函数将后缀表达式求值.代码如下:

#include  #include"caculatefuncs.h" using namespace std; int main(){ string infix; cout<<"输入中缀表达式:"<>infix; string postfix = toPostFix(infix); cout<<"对应的后缀表达式(逆波兰表示法)为"<
       

       

       

       

       
caculatefuncs.h中包含两个函数toPostFix和toDouble的实现.中缀转后缀的算法有一点复杂,规则如下:
       

       
toPostFix函数的实现:
       

       
1 string toPostFix(string infix){ //中缀表达式转后缀表达式函数 2 3 const int n = infix.length(); 4 const char PRI1 = '2'; 5 const char PRI2 = '1'; //优先级定义 6 const char UN = '0'; 7 string postfix( n, ' '); //预留后缀表达式字符串 8 string priority( n, ' '); //预留优先级字符串 9 int i = 0; // infix序数 10 int j = 0; //priority序数 11 int k = 0; //postfix序数 12 13 for( ; i < n; i++){ 14 if(infix.at(i) >= '0' && infix.at(i) <= '9') 15 postfix.at(k++) = infix.at(i); //数字直接存入 16 17 else{ 18 19 switch(infix.at(i)){ 20 case '+': priority.at(j++) = PRI2; 21 break; 22 case '-': priority.at(j++) = PRI2; 23 break; 24 case '*': priority.at(j++) = PRI1; 25 break; 26 case '/': priority.at(j++) = PRI1; 27 break; 28 case '(': priority.at(j++) = UN; 29 break; 30 case ')': while(charStack.top() != '('){ 31 postfix.at(k++) = charStack.top(); 32 charStack.pop(); 33 j--; 34 } 35 charStack.pop(); 36 j--; 37 break; 38 default: cout<<"运算符错误,程序退出"< 1 && priority.at(j-1) < priority.at(j-2) && priority.at(j-1) != UN && priority.at(j-2) != UN){ //当前运算符优先级比栈顶运算符低,则待高优先级运算符弹栈后入栈 42 postfix.at(k++) = charStack.top(); 43 charStack.pop(); 44 charStack.push(infix.at(i)); 45 priority.at(j-2) = priority.at(j-1); 46 j--; 47 } 48 else if( infix.at(i) != ')') 49 charStack.push(infix.at(i)); 50 if( j > 1){ 51 for( int m = j-2; (m >=0)&&(priority.at(m) > priority.at(j-1)); m--){//优先级比较,高于当前运算符优先级的弹栈 52 if(priority.at(m) != UN && priority.at(j-1) != UN ){ 53 postfix.at(k++) = charStack.top(); 54 charStack.pop(); 55 j--; 56 } 57 } 58 } 59 } 60 } 61 while( !charStack.empty()){ //栈中字符全部弹出 62 postfix.at(k++) = charStack.top(); 63 charStack.pop(); 64 } 65 postfix = postfix.substr(0, k); 66 return postfix; 67 }
       

       
至于后缀表达式求值的算法,我们都比较熟悉了.遍历后缀表达式,若是操作数,则压入栈;若为运算符,则从栈中弹出两个操作数,进行计算,然后将计算结果压栈.直至遍历完成时,栈为空.
       
toDouble函数的实现:
       

       
1 double toDouble(string postfix){ //逆波兰表示法转换为整数函数 2 3 const int n = postfix.length(); 4 double a = 0; //第一个操作数 5 double b = 0; //第二个操作数 6 7 for(int i = 0; i < n; i++){ 8 char temp = postfix.at(i); 9 if(temp >= '0' && temp <= '9') //是数字则压栈 10 doubleStack.push( temp- '0'); 11 else{ //运算符分情况讨论 12 switch(temp){ 13 case '+': b = doubleStack.top(); 14 doubleStack.pop(); 15 a = doubleStack.top(); 16 doubleStack.pop(); 17 doubleStack.push(a + b); //运算结果压栈 18 break; 19 case '-': b = doubleStack.top(); 20 doubleStack.pop(); 21 a = doubleStack.top(); 22 doubleStack.pop(); 23 doubleStack.push(a - b); 24 break; 25 case '*': b = doubleStack.top(); 26 doubleStack.pop(); 27 a = doubleStack.top(); 28 doubleStack.pop(); 29 doubleStack.push(a * b); 30 break; 31 case '/': b = doubleStack.top(); 32 if(b == 0){ 33 cout<<"除零异常,程序退出"<
       

       
这个简单计算器实现只能处理10以内的整数,但结果可以为浮点数.可以处理括号,考虑运算符优先级.栈的是运用了C++的模板类Stack,类声明被包含在头文件stack中.本程序使用的两个栈定义如下:
       
stack charStack; //存放字符的栈 stack doubleStack; //存放整数的栈
       
谢谢大家!转载请注明出处,谢谢合作!:http://www.cnblogs.com/Agent-YRBlogs/p/5987603.html