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 *p)100 {101     char a,b,c,d,e,f;102     int i,j;103     SqStack S1,S2;//S1为操作符栈，S2为操作数栈104     InitStack(S1);105     InitStack(S2);106     c=*p++;107     while(c!=‘#‘)108     {109          if(c>=48&&c<=57) Push(S2,c);//输入为数字110          if(c==‘(‘) Push(S1,c); //输入为左括号111          if(c==‘)‘)//输入为右括号112          {113              if(!EmptyStack(S1)) GetTop(S1,e);114              while(e!=‘(‘)115              {116                  Pop(S2,a);117                  Pop(S2,b);118                  Pop(S1,d);119                  if(d==‘+‘) j=(b-48)+(a-48);120                  if(d==‘-‘) j=(b-48)-(a-48);121                  if(d==‘*‘) j=(b-48)*(a-48);122                  if(d==‘/‘)123                  {124                      if(a-48) j=(b-48)/(a-48);125                      else {cout<<"计算过程出现除数为零的错误！"<<endl; return 0;}126                  }127                  f=char(j+48);128                  Push(S2,f);129                  if(!EmptyStack(S1)) GetTop(S1,e);//直到遇到左括号130                  if(e==‘(‘) Pop(S1,e);131              }132          }133          if(c==‘+‘||c==‘-‘||c==‘*‘||c==‘/‘)134          {135              if(EmptyStack(S1))  Push(S1,c);136              else137              {138                  GetTop(S1,e);139                  i=Precede(e,c);140                  if(i==0)141                  {142                      Pop(S2,a);143                      Pop(S2,b);144                      Pop(S1,d);145                      if(d==‘+‘) j=(b-48)+(a-48);146                      if(d==‘-‘) j=(b-48)-(a-48);147                      if(d==‘*‘) j=(b-48)*(a-48);148                      if(d==‘/‘)149                      {150                          if(a-48) j=(b-48)/(a-48);151                          else {cout<<"计算过程出现除数为零的错误！"<<endl; return 0;}152                      }153                      f=char(j+48);154                      Push(S1,c);155                      Push(S2,f);156                  }157                  if(i==1) Push(S1,c);158              }159          }160          c=*p++;161     }162     if(!EmptyStack(S1))163     {164         while(!EmptyStack(S1))165         {166              Pop(S2,a);167              Pop(S2,b);168              Pop(S1,d);169              if(d==‘+‘) j=(b-48)+(a-48);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              f=char(j+48);174              Push(S2,f);175         }176     }177     //最后输出结果178     Pop(S2,a);179     i=a-48;180     cout<<"运算结果为:"<<i<<endl;181     return 0;182 }183 184 185 int main()186 {187     //数据测试188     char *p1="3+2*5#";//=13189     char *p2="2*5+3#";//=13190     char *p3="((3+5*2)+2)/5+6/3*2+3#";//=10191     char *p4="9+(3-1)*3+6/2#";//=18192     EvaluateExpression(p1);193     EvaluateExpression(p2);194     EvaluateExpression(p3);195     EvaluateExpression(p4);196     return 0;197 }