利用链栈将中缀表达式转化为后缀表达式，然后利用顺序栈进行扫描计算，返回结果
书上的代码
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #define size 50 5 using namespace std; 6 typedef struct node 7 { 8 char data; 9 struct node *next; 10 }*linkstack,stacknode; 11 typedef struct //操作数栈 12 { 13 float data[size]; 14 int top; 15 }opstack; 16 void initstack(linkstack *top) 17 { 18 *top=new stacknode; 19 (*top)->next=NULL; 20 } 21 bool isempty(linkstack top) 22 { 23 if(top->next==NULL) 24 return 1; 25 return 0; 26 } 27 void pushstack(linkstack top,char e) 28 { 29 linkstack p; 30 p=new stacknode; 31 p->data=e; 32 p->next=top->next; 33 top->next=p; 34 } 35 bool popstack(linkstack top,char *e) 36 { 37 if(isempty(top)==1) 38 return 0; 39 linkstack p; 40 p=top->next; 41 *e=p->data; 42 top->next=p->next; 43 return 1; 44 } 45 int getstack(linkstack top,char *e) 46 { 47 if(isempty(top)==1) 48 return 0; 49 linkstack p; 50 p=top->next; 51 *e=p->data; 52 return 1; 53 } 54 /********************关于栈的一些操作********************/ 55 void translate(char str[],char exp[])//扫描的元素优先级高于栈顶元素，则入栈，低于则将栈顶元素放置于后缀表达式中，其中）优先级最低 56 { 57 linkstack s; 58 char ch; 59 char e; 60 int i=0,j=0; 61 initstack(&s); 62 ch=str[i]; 63 i++; 64 while(ch!=' ') /*栈内不能存在右括号，有限等级最低，在碰到左括号之前将元素都送到exp中*/ 65 { 66 switch(ch) 67 { 68 case '(': 69 pushstack(s,ch); 70 break; 71 case ')': //优先级最低，栈内的元素出栈 72 while(getstack(s,&e)&&e!='(') 73 { 74 popstack(s,&ch); 75 exp[j]=e; 76 j++; 77 } 78 popstack(s,&e); //将左括号出栈 79 break; 80 case '+': 81 case '-': 82 while(!isempty(s)&&getstack(s,&e)&&e!='(') 83 { 84 popstack(s,&e); 85 exp[j]=e; 86 j++; 87 } 88 pushstack(s,ch); 89 break; 90 case '/': 91 case '*': 92 while(!isempty&&getstack(s,&e)&&(e=='*'||e=='/'))//先对同等级的出栈 93 { 94 popstack(s,&e); 95 exp[j]=e; 96 j++; 97 } 98 pushstack(s,ch); 99 break; 100 default: 101 while(ch>='0'&&ch<='9') //此方法可以计算多位数，一个多位整数结束后以空格隔开 102 { 103 exp[j++]=ch; //放置于后缀表达式数组中 104 ch=str[i]; //取出下一个中缀表达式字符 105 i++; 106 } 107 i--; 108 exp[j]=' '; 109 j++; 110 } 111 ch=str[i]; 112 i++; 113 } 114 while(!isempty(s)) //将字符串结束符送入数组中 115 { 116 popstack(s,&e); 117 exp[j]=e; 118 j++; 119 } 120 exp[j]=' '; 121 } 122 float compute(char a[]) 123 { 124 opstack *s; 125 s=new opstack; 126 float result=0,x1,x2; 127 s->top=-1; 128 int i=0,value=0; 129 while(a[i]!=' ')//不处理空格 130 { 131 if(a[i]!=' '&&a[i]>='0'&&a[i]<='9') //取出数字 132 { 133 value=0; 134 while(a[i]!=' ') 135 { 136 value=value*10+a[i]-'0'; 137 i++; 138 } 139 s->top++; 140 s->data[s->top]=value; 141 } 142 else 143 { 144 switch(a[i]) 145 { 146 case'+': 147 x1=s->data[s->top]; 148 s->top--; 149 x2=s->data[s->top]; 150 result=x1+x2; 151 s->data[s->top]=result; 152 break; 153 case'-': 154 x1=s->data[s->top]; 155 s->top--; 156 x2=s->data[s->top]; 157 result=x2-x1; 158 s->data[s->top]=result; 159 break; 160 case'*': 161 x1=s->data[s->top]; 162 s->top--; 163 x2=s->data[s->top]; 164 result=x1*x2; 165 s->data[s->top]=result; 166 break; 167 case'/': 168 x1=s->data[s->top]; 169 s->top--; 170 x2=s->data[s->top]; 171 result=x2/x1; 172 s->data[s->top]=result; 173 break; 174 default: 175 break; 176 } 177 i++; 178 } 179 } 180 return result; 181 } 182 int main() 183 { 184 char a[size],b[size]; 185 double f; 186 gets(a); 187 translate(a,b); 188 cout<<b<<endl; 189 cout<<compute(b); //传入后缀表达式 190 return 0; 191 }