目标：
将一个中缀表达式转化为后缀表达式并进行求值。
难点:
1、 数字和符号的区分与提取。2、 数字与符号的线性存储
3、 实数的提取,转化与处理。
4、 括号,负数的提取与处理。
数据结构：
由于转换后的后缀表达式中有整数,实数,符号等多种元素,无法存在一个简单的线性数组中,所以采用结构体数组 S[N]存储后缀表达式,每个结构体 STR 中分别有一个 int 变量
存储整数,一个 float 变量存储实数,一个 char 变量存储符号,另外有一个 int 下标,用来
存储该结构体中存储的是符号,整数,还是实数。
具体实现：
由于要处理的东西较多,所以采取分步实现的方式:1、 先实现较为简单的整数
第一步是最简单的情况,没有括号,没有实数,没有负数。但是第一步要完成整个
程序的框架。
a) 首先是中缀表达式的处理与转化。
先用一个 string 类型的字符串 r1 来暂时存储数字。一个 string 类型的 r2 用作
符号栈。然后从头到尾进行扫描。扫到某一位时,会出现两种情况:
1 ）此位是数字这表示当前位是数字的一部分,将它压入 r1
2 ）此位是符号这表示已经扫描完某一个数字,r1 中已经有一个待处理的数字,这时将
r1 转化为整数,累加总项数,放入 S 中,并把标记变量设为 0,代表这是一个数字。同时,在字符栈 r2 中,从栈顶开始,遇到优先级大于当前位的符号,便
出栈,累计总项数,并存入 S 中,标记变量设为 1,代表这是一个符号。一直到优先级不大于为止,然后入栈。最后一步,是初始化 r1,来储存新的数字。
b) 扫描完毕后,进入运算环节。2、 加入实数的处理
扫描 S,遇数字入栈,遇符号出栈两个元素进行计算,计算结果再次入栈。一
直到 S 的末尾。
最后输出栈顶(底)的元素。即结果。
读入过程中 String 类型的字符串数字互转函数使用较为方便,所以直接用函数
处理实数。只需要修改 1 中的判断,当遇到“.”时不退出,而是继续累加,碰到
运算符之后存入时标记变量设为 2,表示实数。
计算过程中,注意“%”操作数的类型要设为 int,“ /”操作数的类型要设为 float。
3、 加入括号的处理与判断
读入过程中,左括号不处理,直接入栈。右括号时,出栈至遇到左括号。
计算过程中,无需特殊处理。
4、 加入负数的提取与处理。
读入过程中,取一个标记变量,标记每一个数是正数还是负数,此变量默认为
1,代表正数。遇到“-”,先判断其头一位和下一位。如果前一位是数字,则记为
减号,如果前一位不是数字,后一位是数字,则表明,这是一个符号。标记变量设
为-1;最后处理后一位所在的数字时,将结果乘上-1,储存,最后将标记变量初始
化为 1。
计算过程中,无需特殊处理。
5、 考虑几种特殊情况
a) –(a+b)
转换成 0–(a+b)。-”先入栈,最后出栈。计算时栈底先压入 0。
b) 其他情况
已在前 4 步中考虑。
CODE：
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<sstream> #define N 200 using namespace std; typedef struct STR { int bj; //标记变量，记录类型 int num; //存储整数 float flo; //存储实数 char fh; //存储符号 } ; int su=0; STR S[N]; //若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于找顶符号（乘除优先加减） //则栈顶元素依次出找并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。 void init() { int cmpn[N]; cmpn[(int)'-']=1; cmpn[(int)'+']=1; cmpn[(int)'*']=2; cmpn[(int)'/']=2; cmpn[(int)'%']=2; cmpn[(int)'^']=3; cmpn[(int)'(']=0; string f; cin>>f; string r1="",r2=""; int ii=0; int fla=1; int fl2=0; for (int i=0;i<f.length();i++) //逐位扫描 { if (f[i]>='0' && f[i]<='9' ) r1+=f[i]; else if (f[i]=='.') //处理实数 { r1+=f[i]; fl2=1; } else { //各种特殊情况 if ( (f[i]=='-') && ( (f[i+1]>='0' && f[i+1]<='9'&&!(f[i-1]>='0' && f[i-1]<='9') )|| i==0)) { if (f[i+1]>='0' && f[i+1]<='9') { fla*=-1; continue; } else if (f[i+1]=='(') { r2[ii]=f[i]; ii++; continue; } } if (f[i-1]>='0' && f[i-1]<='9') { if (fl2==0) { int n = atoi(r1.c_str()); n*=fla; fla=1; cout<<n<<" "; r1=""; S[su].num=n; S[su].bj=0; su++; } else { float n=atof(r1.c_str()); n*=(float)fla; fla=1; cout<<n<<" "; r1=""; S[su].flo=n; S[su].bj=2; su++; fl2=0; } } char ff=f[i]; if (ii==0) { r2[ii]=ff; ii++; } else if (ff=='(') { r2[ii]=ff; ii++; } else if (ff==')') { while (r2[ii-1]!='(') { cout<<r2[ii-1]<<" "; S[su].fh=r2[ii-1]; S[su].bj=1; su++; ii--; } ii--; } else { //cout<<endl<<" "<<cmpn[(int)r2[ii-1]]<<" "<<endl; //cout<<endl<<" "<<cmpn[(int)ff]<<" "<<endl; while (cmpn[(int)r2[ii-1]]>=cmpn[(int)ff]) { if (ii==0)break; cout<<r2[ii-1]<<" "; S[su].fh=r2[ii-1]; S[su].bj=1; su++; ii--; } r2[ii]=ff; ii++; } } } //最后一位 if (f[f.length()-1]>='0'&&f[f.length()-1]<='9') { if (fl2==0) { int n = atoi(r1.c_str()); n*=fla; fla=1; cout<<n<<" "; r1=""; S[su].num=n; S[su].bj=0; su++; } else { float n=atof(r1.c_str()); n*=(float)fla; fla=1; cout<<n<<" "; r1=""; S[su].flo=n; S[su].bj=2; su++; fl2=0; } } while(ii>0) { cout<<r2[ii-1]<<" "; S[su].fh=r2[ii-1]; S[su].bj=1; su++; ii--; } cout<<endl; return; } void calcu() { int ii=1; float sta[N]; sta[0]=0; for (int i=0;i<su;i++) { if (S[i].bj==0) { sta[ii]=S[i].num; ii++; } else if (S[i].bj==2) //实数 { sta[ii]=S[i].flo; ii++; } else { float b1=sta[ii-1]; ii--; float b2=sta[ii-1]; ii--; float re; if (S[i].fh=='+') { re=b2+b1; } else if (S[i].fh=='-') { re=b2-b1; } else if (S[i].fh=='*') { re=b2*b1; } else if (S[i].fh=='/') { re=(float)b2/(float)b1; } else if (S[i].fh=='%') { re=(int)b2%(int)b1; } else if (S[i].fh=='^') { int bb2=1; for (int k=0;k<b1;k++) bb2*=b2; re=bb2; } sta[ii]=re; ii++; } } cout<<sta[ii-1]; return ; } int main() { init(); //读入 calcu(); //计算 return 0; }
