中缀表达式转为后缀表达式并求值

实验报告

课程名称：数据结构与算法

课程类型：必修

实验项目名称：线性表的实现与应用

实验题目：中缀表达式转成后缀表达式并求值

班级：1203103

学号：1120310321

姓名：张文博

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

1.练习栈的创建和常规操作，例：置空栈，判断空栈，返回栈顶元素，压栈，出栈……

2.学习中缀表达式和后缀表达式的定义和表示方法。

3.学习中缀表达式和后缀表达式的存储和输出。

4.学习中缀表达式转化为后缀表达式。

5.学习后缀表达式的求值。

6.练习编写循环程序的算法。

二、实验要求及实验环境

实验要求：输入中缀表达式，把中缀表达式转化为后缀表达式，输出后缀表达式，并对后缀表达式进行求值输出，其中能运行算术四则运算和求模运算。

实验环境：codeblocks

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

1.逻辑结构：线性结构

2.物理结构：线性存储结构中的顺序结构，即用数组和栈存储数据。

本实验中定义了两种线性表形式：数组和栈。用字符型数组存储输入的字符串和和转化为的后缀表达式。在把中缀表达式转化为后缀表达式时，用字符栈存储字符串中的字符，并永远保证栈顶的字符优先级最高；在进行后缀表达式求值时，用数据栈存储数字，按顺序存储，遇到字符时，从栈顶依次弹出两个数据。此外，还定义了一些整型和字符型变量，用于辅助程序的正确运行。

主函数中调用change函数，把中缀表达式转化为后缀表达式；主函数调用operate函数，进行算术式的运算。Change函数调用precede 函数，进行字符优先级的比较。主函数和change函数都调用in函数，进行是否为字符的判断。此外，主函数和change函数都有调用initstack 函数，push函数，pop函数，gettop函数……来帮助函数的运行。

我编写程序的大致思路：

1.中缀表达式转为后缀表达式

首先是遇见数字存入数组，遇见字符压栈，并且先把字符栈底压入一个‘#’。当遇见‘（’时，根据下一个字符是否是‘-’来判断是否是负数。若有‘-’，是负数，存入数组，若没有，把‘（’压栈。例：（-5）。当遇见‘）’时，开始把运算符弹栈，直到遇到‘（’。

当遇见其他运算符时，根据比较与字符栈顶元素的优先级决定如何压栈。优先级设定：#为0，（）为1，+-为2，*/%为3。当栈顶元素的优先级大于等于此运算符时，弹栈进入数组，否则把该运算符压栈。

2.求后缀表达式的值

遇见数字时压栈，遇见运算符时从栈中弹出两个，进行运算。

遇见‘-’时，根据后一位元素是否为数字，进而判断是负号，还是减号，若是负号，求出该负数对应的正数，再取反压栈即可。

遇见浮点数数时，先求小数点前面的整数部分，再求小数点后面整数部分，根据位数a，除以10*a，即可得到小数部分，小数部分与整数部分相加即为该浮点数，压栈即可。

开始

输入中缀表达式

并存储到数组中

调用change函数，

把中缀表达式转

化为后缀表达式

输出相应的

后缀表达式

计算后缀表

达式的值

输出后缀表

达式的值

结束四、测试结果

输入中缀表达式输出后缀表达式结果

(2.5*4+5)/3 2.5 4 * 5 + 3 / 5

(-5)+10*2/(-4) -5 10 2 * -4 / + -10

五、系统不足与经验体会

系统不足：没有完全考虑输错情况下，程序该如何操作，进而导致程序的健壮性不好，此外，没有过多的考虑由于外面因素，程序错误运行的情况。

经验体会：1.对栈的操作要深刻明白先进后出，后进

数据的位于栈顶。

2.数组是按址调用，在调用函数内可以改变

其值。

3.程序循环运行每轮结束后，一定要记得释

放内存，或清空数组里的内容。

4.小数和负数要特殊考虑，编写合适的算法。

5.条件语句中的条件要慎重考虑，反复斟酌。

六、附录：源代码（带注释）

#include

#include

#define SIZE 100#define ERROR 0

typedef struct //定义数据栈

{

float data[SIZE];

int top;

int base;

} SqStack_f;

typedef struct //定义字符栈

{

char data[SIZE];

int top;

int base;

} SqStack_c;

char OPSET[8]= {'+' , '-' , '*' , '/' ,'%','(' , ')' , '#'}; //定义OPSET字符数组为算符集合

void InitStack_f(SqStack_f *s) //置数据栈S为空

{

s->top=0;

s->base=0;

}

void InitStack_c(SqStack_c *s) //置字符栈S为空{

s->top=0;

s->base=0;

}

int Empty_f(SqStack_f *s) //判定s是否为空栈{

if(s->base==s->top)

return 1;

else

return 0;

}

int Empty_c(SqStack_c *s) //判定s是否为空栈{

if(s->base==s->top)

return 1;

else

return 0;}

float GetTop_f(SqStack_f *s)//若数据栈非空，则返回s的栈顶元素；否则返回ERROR

{

if(s->top==s->base)

return ERROR;

return (s->data[s->top-1]);

}

char GetTop_c(SqStack_c *s)//若字符栈非空，则返回s的栈顶元素；否则返回ERROR

{

if(s->top==s->base)

return ERROR;

return (s->data[s->top-1]);

}

void Push_f(SqStack_f *s,float e)//插入e为新的栈顶元素{

s->data[s->top]=e;

s->top++;}

void Push_c(SqStack_c*s,char e)//插入e为新的栈顶元素

{

s->data[s->top]=e;

s->top++;

}

float Pop_f(SqStack_f *s)//若数据栈不空，则删除之，并返回栈顶值；否则返回REEOR

{

float e;

if(s->base==s->top)

return ERROR;

else

{

e=s->data[s->top-1];

s->top--;

}

return e;

}

{

char e;

if(s->base==s->top)

return ERROR;

else

{

e=s->data[s->top-1];

s->top--;

}

return e;

}

int In(char s,char *TestOp)//s为待判断字符，TestOp为已知的算符集合

{

int Find=0,i;

for ( i=0; i<8; i++)

{

if (s == TestOp[i])

{

Find= 1;}

}

return Find;

}

int precede(char Top_char,char s1_char)//判断优先级{

int i,pre[2];

char op[2];

op[0]=Top_char;

op[1]=s1_char;

for(i=0; i<2; i++)

{

switch(op[i])

{

case'#':

pre[i]=0;

break;

case'(':

case')':

pre[i]=1;break;

case'+':

case'-':

pre[i]=2;

break;

case'*':

case'/':

case'%':

pre[i]=3;

break;

}

}

if(pre[0]>=pre[1])

return 1;

else

return 0;

}

void Change(char *s1,char *s2)//将中缀表达式转为后缀表达式{

SqStack_c OPTR;

char ch;

int i=0,j=0;

InitStack_c(&OPTR);

Push_c(&OPTR,'#');

while(s1[i]!='\\0')

{

if(!In(s1[i],OPSET)) //不是运算符则进数组

{

while((s1[i]>='0'&&s1[i]<='9')||s1[i]=='.')

{

s2[j++]=s1[i];

i++;

}

s2[j++]=' ';//存入一个空格

}

else

{

switch(s1[i])

{

case '(':

i++;

if(s1[i]=='-')//此处判断是否是负数，若是，把负数存入数组，若不是，把运算符存入堆栈。

{

while(s1[i]!=')')

{

s2[j++]=s1[i];

i++;

}

s2[j++]=' ';//存入一个空格

i++;

}

else

{

i--;

Push_c(&OPTR,s1[i]);

i++;

}

break;

case ')':

ch=Pop_c(&OPTR);

do //输出括号内的所有运算符 {s2[j++]=ch;

s2[j++]=' ';//补入一个空格作为间隔

ch=Pop_c(&OPTR);

}

while(ch!='(');

i++;

break;

default:

while(precede(GetTop_c(&OPTR),s1[i]))//判断运算符的优先级，始终保存栈顶的优先级最高

{

s2[j++]=Pop_c(&OPTR);

s2[j++]=' ';//补入一个空格作为间隔

}

Push_c(&OPTR,s1[i]);

i++;

}

}

}

while(GetTop_c(&OPTR)!='#')//当s1扫描完成后，把运算符栈中的运算符全部输出存入数组s2

{s2[j++]=Pop_c(&OPTR);

s2[j++]=' ';//补入一个空格作为间隔

}

}

float Operate(float a,char theta, float b)//返回a与b间theta 运算的结果

{

int d,e;

switch(theta)

{

case '+':

return a+b;

break;

case '-':

return a-b;

break;

case '*':

return a*b;

break;

case '/':

if(b==0){

printf("Error Divisor is 0\\n"); return ERROR;

}

return a/b;

break;

case '%':

d=(int)a;

e=(int)b;

if(e==0)

{

printf("Error Divisor is 0\\n"); return ERROR;

}

return (float)(d%e);

break;

default:

printf("Error\\n");

return ERROR;

}

}

{

SqStack_f OPND;

char c,ch;

int i=0,step=0,j=0;

float a=0,b=0,s=0 ;

do

{

i=0;

char receive[100]= {0},exp[100]= {0};

InitStack_f(&OPND);

printf("请输入一个中缀表达式：\\n");

gets(receive); //输入中缀表达式,负数的输入必须要加括号，eg：（-5）+6

Change(receive,exp);

printf("相应的后缀表达式为：\\n");

puts(exp); //输出对应的后缀表达式

ch=exp[0];

while(ch!='\\0') //计算后缀表达式的值

{

if(!In(exp[i],OPSET))//不是运算符则压入栈中

{

s=0;

a=b=step=0;

while(exp[i]>='0'&&exp[i]<='9'&&exp[i]!='.'&&exp[i]!=' ')//算出小数点前面的整数数值

{

s=10*s+exp[i]-48;

i++;

}

if(exp[i]=='.') //满足此条件的为小数，算出小数点后面的数值

{

i++;

while(exp[i]>='0'&&exp[i]<='9'&&exp[i]!=' ')

{

b=10*b+exp[i]-48;

i++;

step++;

}

{

b=b/10;

}

}

a=s+b; //一个数的整数部分和小数部分相加，赋于a

Push_f(&OPND,a);

ch=exp[++i];

}

else if(exp[i]=='-') //判断-为减号还是负号 {

i++;

if(exp[i]>='0'&&exp[i]<='9') //满足此条件为负号，计算出该负数，并压入堆栈

{

s=0;

a=b=step=0;

while(exp[i]>='0'&&exp[i]<='9'&&exp[i]!='.'&&exp[i]!=' ')//算出小数点前面的整数数值{

s=10*s+exp[i]-48;

i++;

}

if(exp[i]=='.')//满足此条件的为小数，算出小数点后面的数值

{

i++;

while(exp[i]>='0'&&exp[i]<='9'&&exp[i]!=' ')

{

b=10*b+exp[i]-48;

i++;

step++;

}

for(j=0; j{

b=b/10;

}

a=-(s+b);//一个数的整数部分和小数部分相加，赋于a并取反，即为该负数值

Push_f(&OPND,a);

ch=exp[++i];

}

else //此时-为减号，按运算符进行运算

{

b=Pop_f(&OPND);

a=Pop_f(&OPND);

Push_f(&OPND,Operate(a,ch,b));

ch=exp[++i];

}

}

else //按相应的运算符进行计算

{

b=Pop_f(&OPND);

a=Pop_f(&OPND);

Push_f(&OPND,Operate(a,ch,b));

i+=2;

ch=exp[i];}

}

printf("后缀表达式的值为：%g\\n

c=getchar();

getchar();

}

while(c=='Y'||c=='y'); //处理是否想要继续操作

return 0;

}