1 #include <iostream> 2 #include<stdlib.h> 3 4 using namespace std; 5 6 #define STACK_INIT_SIZE 100 7 #define STACKINCREASE 10 8 9 //为了简化函数，数据栈和符号栈用了一种结构体(虽然我知道可以用共用体解决问题，嫌烦), 10 //由此导致的后果是接下来所有的运算过程中不允许出现小数,而且由于是利用ASCII表来储存整数, 11 //所以要求运算数以及运算过程中数不能超过表中的最大值,暂时没有考虑负数问题，而且不能在输入时出现两位数 12 //以上问题全是由于我把数字当成字符处理的结果，单纯图个方便 13 typedef struct 14 { 15 char *base; 16 char *top; 17 int stacksize; 18 }SqStack; 19 20 21 int InitStack(SqStack &S) 22 { 23 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char)); 24 if(!S.base) 25 { 26 cout<<"分配空间失败!"; 27 exit(-1); 28 } 29 S.top=S.base; 30 S.stacksize=STACK_INIT_SIZE; 31 return 0; 32 } 33 34 35 int Push(SqStack &S,char e) 36 { 37 if((S.top-S.base)>=STACK_INIT_SIZE) 38 { 39 S.base=(char *)realloc(S.base,(STACK_INIT_SIZE+STACKINCREASE)*sizeof(char)); 40 if(!S.base) 41 { 42 cout<<"分配空间失败!"; 43 exit(-1); 44 } 45 S.top=S.base+STACK_INIT_SIZE; 46 S.stacksize=STACK_INIT_SIZE+STACKINCREASE; 47 } 48 *(S.top)=e;//结构体 49 S.top++; 50 return 0; 51 } 52 53 54 int Pop(SqStack &S,char &e) 55 { 56 if(S.base==S.top) 57 { 58 cout<<"栈为空!"; 59 exit(0); 60 } 61 S.top--; 62 e=*(S.top); 63 return 0; 64 } 65 66 int GetTop(SqStack &S,char &e) 67 { 68 if(S.base==S.top) 69 { 70 cout<<"栈为空!"; 71 return 0; 72 } 73 else 74 { 75 e=*(S.top-1); 76 return 1; 77 } 78 } 79 80 81 int EmptyStack(SqStack &S) 82 { 83 if(S.base==S.top) return 1;//stack is empty! 84 else return 0;//stack is not empty! 85 } 86 87 88 int Precede(char a,char b)//a为符号栈栈顶元素,b为待插入的元素 89 { 90 int i;//i=1入栈,i=0弹出操作符以及操作数进行计算 91 if((a=='+'||a=='-')&&(b=='*'||b=='/')) i=1; 92 if((a=='+'||a=='-')&&(b=='+'||b=='-')) i=0; 93 if((a=='*'||a=='/')&&(b=='*'||b=='/')) i=0; 94 if((a=='*'||a=='/')&&(b=='+'||b=='-')) i=0; 95 if(a=='(') i=1; 96 return i; 97 } 98 99 int EvaluateExpression(char *q) 100 { 101 char *p = q; 102 char a,b,c,d,e,f; 103 int i,j; 104 SqStack S1,S2;//S1为操作符栈，S2为操作数栈 105 InitStack(S1); 106 InitStack(S2); 107 c=*p++; 108 while(c!='#') 109 { 110 if(c>=48&&c<=57) Push(S2,c);//输入为数字 111 if(c=='(') Push(S1,c); //输入为左括号 112 if(c==')')//输入为右括号 113 { 114 if(!EmptyStack(S1)) GetTop(S1,e); 115 while(e!='(') 116 { 117 Pop(S2,a); 118 Pop(S2,b); 119 Pop(S1,d); 120 if(d=='+') j=(b-48)+(a-48); 121 if(d=='-') j=(b-48)-(a-48); 122 if(d=='*') j=(b-48)*(a-48); 123 if(d=='/') 124 { 125 if(a-48) j=(b-48)/(a-48); 126 else {cout<<"计算过程出现除数为零的错误！"<<endl; return 0;} 127 } 128 f=char(j+48); 129 Push(S2,f); 130 if(!EmptyStack(S1)) GetTop(S1,e);//直到遇到左括号 131 if(e=='(') Pop(S1,e); 132 } 133 } 134 if(c=='+'||c=='-'||c=='*'||c=='/') 135 { 136 if(EmptyStack(S1)) Push(S1,c); 137 else 138 { 139 GetTop(S1,e); 140 i=Precede(e,c); 141 if(i==0) 142 { 143 Pop(S2,a); 144 Pop(S2,b); 145 Pop(S1,d); 146 if(d=='+') j=(b-48)+(a-48); 147 if(d=='-') j=(b-48)-(a-48); 148 if(d=='*') j=(b-48)*(a-48); 149 if(d=='/') 150 { 151 if(a-48) j=(b-48)/(a-48); 152 else {cout<<"计算过程出现除数为零的错误！"<<endl; return 0;} 153 } 154 f=char(j+48); 155 Push(S1,c); 156 Push(S2,f); 157 } 158 if(i==1) Push(S1,c); 159 } 160 } 161 c=*p++; 162 } 163 if(!EmptyStack(S1)) 164 { 165 while(!EmptyStack(S1)) 166 { 167 Pop(S2,a); 168 Pop(S2,b); 169 Pop(S1,d); 170 if(d=='+') j=(b-48)+(a-48); 171 if(d=='-') j=(b-48)-(a-48); 172 if(d=='*') j=(b-48)*(a-48); 173 if(d=='/') j=(b-48)/(a-48); 174 f=char(j+48); 175 Push(S2,f); 176 } 177 } 178 //最后输出结果 179 Pop(S2,a); 180 i=a-48; 181 while(*q!='#') cout << *q++; 182 cout << " 的运算结果为:"<<i<<endl; 183 return 0; 184 } 185 186 187 int main() 188 { 189 //数据测试 190 char *p1="3+2*5#";//=13 191 char *p2="2*5+3#";//=13 192 char *p3="((3+5*2)+2)/5+6/3*2+3#";//=10 193 char *p4="9+(3-1)*3+6/2#";//=18 194 EvaluateExpression(p1); 195 EvaluateExpression(p2); 196 EvaluateExpression(p3); 197 EvaluateExpression(p4); 198 return 0; 199 }
思路参考：http://www.cnblogs.com/dolphin0520/p/3708602.html