中缀表达式转换为后缀表达式c++b编程

设计成绩 报告成绩 指导老师 一．实验目的

掌握线性表的使用，熟练掌握栈的各种操作函数，能借助于栈的功能将中缀表达式转换为后缀表达式，并利用后缀表达式求值。 二．实验要求及实验环境 实验要求：1.使用栈来进行操作

2.能提示用户输入正确的中缀表达式的值，并输出正确的后缀表达式 3.利用后缀表达式求值并输出 实验环境：CodeBlocks(visual stdio)/win 7系统

三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系） 主要的数据类型：

Word结构体类型的定义，含有两个变量字符型和double型 栈类型的定义，其中数组类型为word型，栈的各种操作函数的定义 主函数int main()中

char mid[100] 存放用户输入的中缀表达式

int m 记录用户输入的中缀表达式所含的字符数

word m_word[100] 可将中缀中的字符和数字分开存放在两个不同类型的数组中，并实现将连续的多位整数至于统一存储空间 word post[100] 存放转换后的后缀表达式的值 int l 记录后缀表达式所含字符长度 int r 存放根据后缀表达式所求的值

在分开存储中缀表达式的运算符和数字的void analysis(char post[100],word m_word[100])函数中

char post[100] 存放中缀表达式

word m_word[[100] 结构体类型的数组可以区分多位数，小数，运算符 double sum 由字符转换后的多位数或小数

依次扫描中缀表达式的字符，若连续的为一串数字，则将他们转换为多位数，

存放于word 类型的m_word数组中并且型为num下，所下标对应的型为type置‘0’，若为操作符，则直接存于m_word数组中并且型为type下。 在表达式转换void Exchange(word a[100],word b[100],int m,int &l)函数中 word a[100] 存放的是中缀表达式 word b[100] 存放转换后的后缀表达式 int m 标记数组a中元素个数 int l 标记数组b中元素个数

STACK O 临时存放运算符（ + - * / ）并对其进行相应的入栈出栈弹栈操作

在求值double Add(word post[100],int l)函数中 word post[100] 后缀表达式结构体数组 int l 记录数组长度

STACK S 将后缀表达式的数字按某种方式压入此栈，经过运算后弹出

最后一个元素即为所求的值

1. 逻辑设计：（1）输入中缀表达式

2. 借助analisis,将输入的单一字符变为相应的整数和小数，存放在一结构体数组中，此数组可区分数和操作符

3.将中缀表达式转换为后缀表达式需要借助于一个栈来存放操作符，具体方法如下：

①从左到右一次扫描中缀表达式的每一个字符，如果为多位数或浮点数，则直接将它们写入后缀表达式中。

②如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕。 ③如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：

●1、当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表式，

并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级； ●2、当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。 ④重复上述步骤，直到将中缀表达式扫描完毕，最后弹出栈中的所有元素并放入后缀表达式中，转换结束。

(3)求后缀表达式式的值，将后缀表达式中的数字直接压入新栈中，若为运算符，则将栈顶元素和次栈顶元素做相应的运算，则新栈中存储的最后一个值为我们所求的表达式的结果。

流程图见下页：

主程序的流程图为：

开始 int main 函数 输出表达式的运算结果 提示用户输入中缀表达式 analysis函数 将中缀表达式存入结构体数组中 Exchange函数 将中缀表达式转换为后缀表达式 输出后缀表达式 Add函数 后缀表达式求值 结束

中缀表达式的等价转换analysis函数流程图：

依次扫描输入的中缀表达式 扫描字符为0至9间的任意字符时 为操作符时 循环扫描下一位直到它不为数字 下一位为‘.’ 存入结构体数组型为type中 转换为多位数或小数存入结构体数组型为Num中,将type型置空

中缀表达式转换为后缀表达式的Exchange函数流程图：

建立操作符栈 判断表达式数组中字符属性 若为数字 若为‘（’ 若为‘）’ 与栈顶元素优先级比较 存入后缀表达式数组中 压入操作符栈 弹出栈中元素 小于等于 大于 取栈顶元素放入数组，直到优先级大于，并压栈 压栈 栈非空 弹出存入数组 输出

根据后缀表达式求值Add函数流程图：

判断数组中元素属性 若为数字 若为操作符 直接入栈 弹出栈顶和次栈顶元素，并转换为整型 根据运算符进行相应操作，将结果入栈 弹出栈顶元素，即为所求的值

四．测试结果

五．系统不足与经验体会

1当输入除数为零时，系统会自动报错，但在程序中并未有报错语句，应该在后期加以改进

2熟练掌握栈的各种操作，是写好本次试验的前提条件

3后期学习中应该加强动手能力，多上机操作试验，因为你永远想不到自己所写的程序会发生什么样的错误 六，附录（源代码，带注释） #include using namespace std; #define maxlength 100

struct word //定义word结构体类型，其中包含两个变量 { };

struct STACK{ //定义栈的结构体类型 };

void MakeNull(STACK &S)//初始化栈 { }

bool Empty(STACK S)//判栈空 { }

word Top(STACK S)//弹出栈顶元素 {

word empty={'0',0}; if(Empty(S))

if(S.top>maxlength-1)

return 1; S.top=maxlength; int top;

word elements[maxlength]; char type; double num;

else

return 0;

}

return empty;

else

return(S.elements[S.top]);

word Pop(STACK &S)//删除栈顶元素 {

if(Empty(S)) { }

return S.elements[S.top++]; }

std::cerr<<\栈空不能出栈\

void Push(word x,STACK &S)//将元素压入栈中 { }

word Display(STACK S) {

word empty={'0',0}; cout<<\栈中元素有\ while(!Empty(S)) {

if (S.top==0) { }

S.top=S.top-1; S.elements[S.top]=x;

std::cerr<<\栈满不能入栈\

empty=Pop(S); cout<

cout<

word iDisplay(STACK S) {

word empty={'0',0}; cout<<\栈中元素有\ while(!Empty(S)) {

empty=Pop(S); cout<

cout<

void Exchange(word a[100],word b[100],int m,int &l) { //将中缀表达式转换为后缀表达式

STACK O; //定义空栈O MakeNull(O); int i;

for(i=0;i

if(a[i].type=='0')//如果为数字时

{

b[l]=a[i];//直接存入后缀表达式数组 l++;

}

if(a[i].type=='(') {

Push(a[i],O);

Display(O);

b[l++]=Pop(O);

if (a[i].type=='+'||a[i].type=='-') {

while(!Empty(O)&&Top(O).type!='(') {

}

Display(O);

Push(a[i],O);

}

Display(O);

while(!Empty(O)&&Top(O).type!='-'&&Top(O).type!='+'&&Top(O).type!

}

if(a[i].type=='/'||a[i].type=='*') {

='(')

b[l++]=Pop(O);

Display(O);

Push(a[i],O);

Display(O);

while(Top(O).type!='(') {

b[l++]=Pop(O);

}

if(a[i].type==')') {

Display(O);

} Pop(O);

Display(O);

}

while(!Empty(O))//当栈非空时，弹出栈顶元素存入后缀表达式数组 {

b[l++]=Pop(O); }

Display(O);

} int j;

for(j=0;j

if (b[j].type=='0') { } else

cout<

}

}

cout<

double Add(word post[100],int l)//求和 {

STACK S; MakeNull(S);

for(int i=0;i

if(post[i].type=='0')//为数字时 {

Push(post[i],S);

iDisplay(S);

} else {

double a,b; a=Pop(S).num;

iDisplay(S);

b=Pop(S).num;

iDisplay(S);

word c; c.type='0';

switch(post[i].type) {

case '+': c.num=b+a;break;

case '-': c.num=b-a;break; case '*': c.num=b*a;break; case '/': c.num=b/a;break;

}

default: break;

Push(c,S);

iDisplay(S);

}

}

double result=Pop(S).num;

iDisplay(S); }

void analysis(char post[100],word m_word[100]) { //将中缀表达式转换为等价的中缀表达式

int i=0,j=0; double sum;

while(post[i]!='#') {

sum=0;

if (post[i]>='0'&&post[i]<='9') {

while(post[i]>='0'&&post[i]<='9') { }

if (post[i]=='.') {

sum*=10;

sum+=(double)(post[i]-'0');//按多位数存储 i++;

return result;

}

}

}

}

i++;

float k=10.0;

while(post[i]>='0'&&post[i]<='9')//按小数存储 { }

sum+=(double)(post[i]-'0')/k; i++; k*=10.0;

m_word[j].type='0'; m_word[j].num=sum; j++;

else { }

m_word[j].type=post[i]; i++;j++;

int main() { double r;

char mid[100]; word m_word[100]; int i=0,m=0;

cout<<\请输入中缀表达式\while(cin>>mid[i]) {

}

if(mid[i]=='#')

break; i++; m++;

}

cout<<\输入的中缀表达式为\for(i=0;i

cout<

cout<

analysis(mid,m_word); word post[100]; int l=0;

cout<<\转换后的后缀表达式为\\n\Exchange(m_word,post,m,l); cout<<\运算结果为\\n\r=Add(post,l); cout<

本文来源：https://www.bwwdw.com/article/frao.html