后缀表达式求值

1、实验报告书课程名： 数据结构题 目： 后缀表达式求值1、实验题目掌握栈“后进先出”的特点。掌握栈的典型应用一一后缀表达式求值。2、实验内容 用键盘输入一个整数后缀表达式(操作数的范围是09,运算符只含+、一、*、/、，而且中间不可以有空格)，使用循环程序从左向右读入表达式。如果读入的是操作数，直接进入操作数栈。如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并将计 算结果存回操作数栈。检验程序运行结果。3、实验要求分析后缀表达式求值的算法思想，用C (或C+ )语音设计程序。上机调试通过实验程序。给出具体的算法分析，包括时间复杂度和空间复杂度等。撰写实验报告(把输入实验

2、数据及运行结果用抓图的形式粘贴到实验报告上)。本程序运行结果通过以后，添加到原教材验证性实验3的菜单中去。4、实验步骤与源程序错误！未找到引用源。实验步骤使用循环从左到右输入后缀表达式。如输入的是运算符，立即从操作数栈取出两个操作数， 计算上述操作数和运算符的值，然后存回操作数栈。如输入的是操作数则直接存入操作数栈。 整个过程只需要一个操作数栈。由一个链栈结点定义node、push ()、pop ()、empty ()运算函数 一个main ()主函数(完成数据输入和函数调用)、两个个功能函数： isoperator() 判运算符 getvalue() 计算表达式值错误！未找到引用源。源代码#

3、includestdlib.h #include错误！未找到引用源。源代码#includestdlib.h #includestdio.h struct nodeint data;struct node *next;typedef struct node stacklist; typedef stacklist *link;link operand=NULL;void push( int value)link newnode;newnode=new stacklist;if (!newnode)printf(分配失败！)；return ;newnodedata二value; newnode-n

4、ext=operand; operand二newnode;return ; void pop(int *value)link top;if (operand !=NULL)top=operand;operand=operandnext; *value=topdata;delete top;else/栈结构声明/数据域/指针域/链表新类型/链表指新针类型/操作数栈指针/进栈，存入数据/新结点指针/分配新结点/存入失败/创建结点的内容/新结点成为栈的开始/出栈，取出数据/指向栈顶/指向栈顶/移动栈顶指针，指向下一个结点/取数据/吸收结点*value=1;int empty()/ 判栈空if (op

5、erand!二NULL)return 1;elseireturn 0;int isoperator(char op)/判运算符switch (op)icase+:case-:case *:case/: return 1;/是运算符，返回default: return 0;/不是运算符，返回/计算表达式值/计算表达式值switch(char)op)case*: return(operandl*operand2); case/: return(operandl/operand2);case+: return(operandl+operand2); case-: return(operandl-op

6、erand2);void main()char exp100;void main()char exp100;int operandl=0;int operand2=0;int result=0;int pos=0; printf(tn请输入后缀表达式：)； gets(exp);/cin.getline(exp,81)printf(tnn后缀表达式%s的结果是:/主函数/定义操作数/定义操作数/定义操作结果变量/目前表达式位置/读取后缀表达式,exp);while (exppos !=0 & exppos !=n)while (exppos !=0 & exppos !=n)/分析表达式字符串i

7、f (isoperator(exppos)/是运算符，取两个操作数pop(&operand2);pop(&operandl);push(getvalue(exppos,operandl,operand2); elsepush(exppos-48);/是操作数，压入操作数栈pos+;/移到下一个字符串位置 pop(&result);/ 弹出结果printf(%dn,result);/ 输出5、测试数据与实验结果(可以抓图粘贴)图1：程序运行结果6、结果分析与实验体会结果分析：本次实验结果准确。按照题目要求得出结果了。算法分析：设后缀表达式长度为n,程序中的栈运算时间复杂度都为：0(1)； 功能函数的时间复杂度也都为：0(1) 主函数复杂度都是为：0 (n)；所以总时间复杂度都是为：0 (n)；总空间复杂度都是为：0 (n)；实验体会:通过了运用课堂所学的知识以及课外的相关知识学习，我掌握了在顺序栈和链栈上实现进栈、 出栈、读栈顶元素、判栈空和判栈满等基本操作。栈是限制在表尾进行插入和删除操作的线性表。 体会到栈的逻辑结构和线性表相同，其主要特性是“后进先出