【数据结构】利用后缀表达式求表达式的值
发布时间：2020-12-15 05:56:04 所属栏目：安全 来源：网络整理
导读：目标： 将一个中缀表达式转化为后缀表达式并进行求值。 难点: 1、 数字和符号的区分与提
|
目标： 将一个中缀表达式转化为后缀表达式并进行求值。 难点: 1、 数字和符号的区分与提取。2、 数字与符号的线性存储 3、 实数的提取,转化与处理。 4、 括号,负数的提取与处理。 数据结构： 由于转换后的后缀表达式中有整数,实数,符号等多种元素,无法存在一个简单的线性数组中,所以采用结构体数组 S[N]存储后缀表达式,每个结构体 STR 中分别有一个 int 变量 存储整数,一个 float 变量存储实数,一个 char 变量存储符号,另外有一个 int 下标,用来 存储该结构体中存储的是符号,整数,还是实数。 具体实现： 由于要处理的东西较多,所以采取分步实现的方式:1、 先实现较为简单的整数 第一步是最简单的情况,没有括号,没有实数,没有负数。但是第一步要完成整个 程序的框架。 a) 首先是中缀表达式的处理与转化。 1 ）此位是数字这表示当前位是数字的一部分,将它压入 r1 b) 扫描完毕后,进入运算环节。2、 加入实数的处理 读入过程中 String 类型的字符串数字互转函数使用较为方便,所以直接用函数 处理实数。只需要修改 1 中的判断,当遇到“.”时不退出,而是继续累加,碰到 运算符之后存入时标记变量设为 2,表示实数。 计算过程中,注意“%”操作数的类型要设为 int,“ /”操作数的类型要设为 float。 3、 加入括号的处理与判断 读入过程中,左括号不处理,直接入栈。右括号时,出栈至遇到左括号。 计算过程中,无需特殊处理。 4、 加入负数的提取与处理。 读入过程中,取一个标记变量,标记每一个数是正数还是负数,此变量默认为 1,代表正数。遇到“-”,先判断其头一位和下一位。如果前一位是数字,则记为 减号,如果前一位不是数字,后一位是数字,则表明,这是一个符号。标记变量设 为-1;最后处理后一位所在的数字时,将结果乘上-1,储存,最后将标记变量初始 化为 1。 计算过程中,无需特殊处理。 5、 考虑几种特殊情况 a) –(a+b) 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;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |