用顺序栈计算表达式

用顺序栈计算表达式

《数据结构》实验报告二

专业：自动化 学号：0901070110 日期：2009、11、17

班级：0701 姓名：皇甫海文 程序名：用顺序栈计算表达式

一、上机实验的问题与要求：

问题描述：利用栈的基本操作实现一个算术表达式的求值的程序。 基本要求：

（1） 定义栈的顺序存取结构。

（2） 分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3） 定义一个函数用来计算表达式结果，并且可以显示表达式的后缀表示。 （4） 设计一个测试主函数进行测试。

二、程序设计的基本思想、原理和算法描述： 采用结构体定义栈：typedef struct

{char fun; int grade;

}Functor; /*定义算符栈结构体*/

程序基本思想：

（1）设表达式作为一个满足表达式语法规则的串存储，如表达式“3*2^(4+2*2-1*3)-5”，它的求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因为后面可能还有更高的运算。正确的处理过程是：需要两个栈，即运算对象栈s1和算符栈s2。当自左向右扫描表达式的每一个字符时，若当前字符是运算对象，则入对象栈；是运算符是，若这个运算符逼栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符“=”。

本规则中的每个运算符栈内、栈外的级别见下表。

（ 方法与前述对中缀表达式求值的方法完全相同，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达是合法的且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法：遇到运算对象则顺序向存储后缀表达式的B组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入近B组中存放。中缀表达式“3*2^(4+2*2-1*3)-5”的后缀表达是 “32422*+13*-^*5-” （3）后缀表达式求值

计算一个后缀表达式，算法上比计算一个中缀表达式简单得多。具体做法：只使用一个对象栈，当从左到右扫描表达式时，每遇一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果在入栈，直到整个表达式结束，这时

用顺序栈计算表达式

送入栈顶的值就是结果。 程序中以“=”为结束符。 三、源程序即注释

#include<stdio.h> #include<conio.h> #include<math.h> #include<stdlib.h> typedef struct {char fun;

int grade;

}Functor; /*定义算符栈结构体*/ Functor FUNCTOR[20];

float NUM[20]; /*定义算符栈和对象栈*/ char ch[100];

int sub=0; /*存放输入流的字符串*/

float Char_To_Num() /*将表示数据的字符串转化成数据*/ {int flag=0, i=-1; float value=0.0;

while((ch[sub]>=48&&ch[sub]<=57)||ch[sub]=='.') {if(ch[sub]=='.')

flag=1; else

{if(flag==0) value=value*10+ch[sub]-48; else

{value=value+(ch[sub]-48)*pow(10,i); i--; } } sub++; }

return value;

}

int In_Grade(char c) /*算符在栈内时的级别*/ {int g; switch(c) {

case '^': g=3;break; case '*': case '/':

case '%': g=2;break; case '+':

case '-': g=1;break;

用顺序栈计算表达式

case '(': g=0;break; case ')': g=-1;break; }

return g; }

int Out_Grade() /*算符在栈外时的级别 */ {int g;

switch(ch[sub]) {

case '^': g=4;break; case '*':

case '/':

case '%': g=2;break; case '+':

case '-': g=1;break; case '(': g=4;break; case ')': g=-1;break; } return g; }

void Error() {

printf("Enter the expression is wrong!\n"); printf("\nPress any key to exit!"); getch(); exit(1); }

void Calculate(int i,int j) {

if(i>=2) /*判断对象栈中元素个数*/ {switch(FUNCTOR[j-1].fun)

{

case '^': NUM[i-2]=pow(NUM[i-2],NUM[i-1]); break; case '*': NUM[i-2]=NUM[i-2]*NUM[i-1]; break;

case '/': NUM[i-2]=NUM[i-2]/NUM[i-1]; break;

case '%': NUM[i-2]=(int)(NUM[i-2])%(int)(NUM[i-1]); break; case '+': NUM[i-2]=NUM[i-2]+NUM[i-1]; break; case '-': NUM[i-2]=NUM[i-2]-NUM[i-1]; break; }

NUM[i-1]=0;

FUNCTOR[j-1].fun=0;

用顺序栈计算表达式

}

else Error(); /*若对象栈若只剩一个数据，则输入的表达式有误*/ }

float Char_Transform() {int i=0,j=0,grade,flag=0;

while(ch[sub]!='='||j!=0)

{if(ch[sub]=='=') /*输入的字符是否取完 */ {Calculate(i,j); i--; j--; }

else

{if(ch[sub]>=48&&ch[sub]<=57) /*判断是否为运算对象 */ { NUM[i++]=Char_To_Num(); if(flag)

{NUM[i-1]=-NUM[i-1]; FUNCTOR[j-1].fun=0; j--; flag=0; }

}

else /*判断是否为算符*/

{if(ch[sub]=='%'||(ch[sub]>=40&&ch[sub]<=43)||ch[sub]=='-'||ch[sub]=='^'||ch[sub]=='/') {if(FUNCTOR[j-1].fun=='-'&&FUNCTOR[j-2].fun=='('&&ch[sub]==')') /*判断是否为负数*/

{NUM[i-1]=-NUM[i-1]; FUNCTOR[j-1].fun=0; FUNCTOR[j-2].fun=0; j=j-2; sub++;

} else …… 此处隐藏：1985字，全部文档内容请下载后查看。喜欢就下载吧 ……