数据结构实验报告 学号：xxxxxxxxxxx 知识范畴：栈与队列 姓名：xxxxxx 专业：计算机科学与技术 完成日期：2019 年 04 月 01 日 实验题目：中缀表达式求值 实验内容及要求： 评分 满分——5 分 从键盘输入中缀表达式，建立操作数与运算符堆栈，计算并输出表达式的求值结果。 基本要求：实现 +, -, *, /四个二元运算符以及（）； 操作数范围为 0 至 9。 提高要求：实现+, -两个一元运算符（即正、负号）； 操作数可为任意整型值（程序可不考虑计算溢出）。 若两个整数相除，结果只保留整数商（余数丢弃）；每位同学可选择实现基本要求或者提 高要求；程序可不处理表达式语法错误。 实验目的：掌握堆栈在表达式求值中的应用。 数据结构设计简要描述： 采用数组作为操作柱栈和操作符栈，操作数用整型存储，操作符用字符类型存储。 算法设计简要描述： 算法采用中缀表达式转化成后缀表达式，再求值的方法实现。 输入/输出设计简要描述： 从键盘输入+，-，*，/，（，）以及 0-9 的操作数，表达式最后输入#时停止。输出的是表 达式求出的值，为整型数据。 编程语言说明： 使用 Linux 自带 vim 编辑器和 gcc 编译器编程。 主要代码采用 C 语言实现 ；输入与输出 采用 C 语言的 putchar 和 printf 流；程序注释采用 C/C++规范 主要函数说明： char pop(char *optr, int *_top) // 操作符元素退栈 void push(char *optr, char ch, int *_top) // 操作符元素进栈 char get_top(char *optr, int *_top) // 获取操作符栈顶元素 int pop_number(int *opnd, int *top) // 操作数元素退栈 void push_number(int *opnd, int number, int *top) // 操作数元素进栈 int get_top_number(int *opnd, int *top) // 获取操作数栈顶元素 int ispTransform(char c) // 栈中运算符优先级转化 int icpTransform(char c) // 栈外运算符优先级转化 int calculate(int *opnd,int *top,char ch) // 计算二元运算数值 void exTransform(char *optr,int *opnd, int *_top, int *top) // 中缀表达式转化为后 缀表达式再求值 1 / 5 

程序测试简要报告： 源程序代码： //Predefine.h #ifndef _PREDEFINE_H #define _PREDEFINE_H 1 // **********操作符处理函数*********** // 操作符元素退栈 char pop(char *optr, int *_top) { char ch = optr[*_top]; (*_top)--; return ch; // 操作符元素进栈 void push(char *optr, char ch, int *_top) { (*_top)++; optr[*_top] = ch; } } } // 获取操作符栈顶元素 char get_top(char *optr, int *_top) { return optr[*_top]; } // **********操作符处理函数*********** // **********操作数处理函数*********** // 操作数元素退栈 int pop_number(int *opnd, int *top) { int number = opnd[*top]; (*top)--; return number; // 操作数元素进栈 void push_number(int *opnd, int number, int *top) { (*top)++; 2 / 5 

opnd[*top] = number; } // 获取操作数栈顶元素 int get_top_number(int *opnd, int *top) { return opnd[*top]; } // **********操作数处理函数*********** // 栈中运算符优先级转化 int ispTransform(char c) { switch(c) { case '#':return 0;break; case '(':return 1;break; case '+':return 2;break; case '-':return 2;break; case '*':return 3;break; case '/':return 3;break; case ')':return 4;break; default: return -1;break; } } // 栈外运算符优先级转化 int icpTransform(char c) { switch(c) { case '#':return 0;break; case '(':return 4;break; case '+':return 2;break; case '-':return 2;break; case '*':return 3;break; case '/':return 3;break; case ')':return 1;break; default: return -1;break; } } // 计算二元运算数值 int calculate(int *opnd,int *top,char ch) { char result; int number1 = pop_number(opnd,top); 3 / 5 

int number2 = pop_number(opnd,top); switch(ch) { case '+':result = number2 + number1;break; case '-':result = number2 - number1;break; case '*':result = number2 * number1;break; case '/':result = number2 / number1;break; default:break; } return result; } // 中缀表达式转化为后缀表达式再求值 void exTransform(char *optr,int *opnd, int *_top, int *top) { char ch1; int temp; push(optr, '#', _top); char ch = getchar(); while(get_top(optr,_top)!='#' || ch!='#') // 读到结束符或者栈空退出 { // 先把‘#’压栈 // 如果不是运算符就进操作数栈 if(ch!='+' && ch!='-' && ch!='*' && ch!='/' && ch!='(' && ch!=')' && ch!='#') { temp = ch - '0'; push_number(opnd,temp,top); ch = getchar(); // 入栈之后接着读下一位 } else { // 判断栈内运算符和站外运算符的优先级 if(ispTransform(get_top(optr,_top)) >= icpTransform(ch)) { // 如果栈内优先级大于或者等于栈外优先级，运算符出栈 ch1 = pop(optr,_top); if(ch1!='(') { } else } else{ } temp = calculate(opnd,top,ch1); push_number(opnd, temp, top); ch = getchar(); push(optr,ch,_top); ch = getchar(); 4 / 5 

} } } #endif // _PREDEFINE_H // main.c #include #include #include "Predefine.h" #define MAX_SIZE 20 int main() { } // 运算符栈顶指针 // 运算数栈顶指针 int top_optr = -1; int top_opnd = -1; char optr[MAX_SIZE]; // 操作符栈，最大容量 MAX_SIZE int opnd[MAX_SIZE]; // 操作数栈，最大容量 MAX_SIZE exTransform(optr,opnd,&top_optr,&top_opnd); printf("%d\n",get_top_number(opnd,&top_opnd)); return 0; 5 / 5