数据结构实验-栈和队列
实验3：栈和队列
一、实验目的
深入了解栈和队列的特性，学会在实际问题下灵活运用它们。
二、问题描述
表达式求值运算是实现程序设计语言的基本问题之一，也是栈应用的一个典型例子。设计并演示用算符优先级对算术表达式的求解过程。
三、实验要求
1、算法优先级别如下：
'+', '-', '*', '/', '(', ')', '#'
'+' '>', '>', '<', '<', '<', '>', '>',
'-' '>', '>', '<', '<', '<', '>', '>',
'*' '>', '>', '>', '>', '<', '>', '>',
>
'/' '>', '>', '>', '>', '<', '>', '>',
'(' '<', '<', '<', '<', '<', '=', ' ',
')' '>', '>', '>', '>', ' ', '>', '>',
'#' '<', '<', '<', '<', '<', ' ', '='
2、以字符序列的形式从终端输入语法正确、不含变量的算术表达式，利用给出的算符优先级关系，实现对算术四则混合运算的求解过程。
四、实验环境
PC微机
DOS操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境
五、实验步骤
1、根据给出的算符优先级，设置运算符栈和运算数栈；
2、[
3、在读入表达式的同时，完成运算符和运算数的识别处理，并将运算数的字符序列形
式转换成整数形式，并进行相应的运算；
4、调试程序，检查输出结果；
5、实验小结。
六、测试数据
1.输入数据：1+（20+4）/（4-1）
正确结果：9
2.输入数据：2*9-6-（20+4）/（4-1）
正确结果：4
七、实验报告要求
实验报告应包括以下几个部分：
1、问题描述；
；
2、算法的设计描述；
3、测试结果的分析与讨论。
4、设计与实现过程中的体会，进一步的改进设想。
实现算法的程序清单，应有足够的注释。
实验代码如下：
#include
#include
#include
using namespace std;
#define MAX 1000
struct save1
{
float n[MAX];
int top;
}stack1;
struct save2
{
char n[MAX];
int top;
}stack2;
bool stackempty(save1 s) {
if(line[i]=='.') nofpoint++;
temp[j++]=line[i];
i++;
if(i>=len) break;
}
if( nofpoint>1 || (i { cout<<"表达式有错"< 存数中含有不止一个小数 点，或者数字后面跟的不是 “+、-、*、/、^、)”，则 为错误 temp[j]='\0'; b=atof(temp); push(stack1,b); if(i>=len) break; } else { if(line[i]=='-' || line[i]=='+' || line[i]=='*' || line[i]=='/' || line[i]=='^' || line[i]=='(' || line[i]==')' ) //若读入 的字符为运算符的情况 { g=1; if(line[i]=='(' && i==len) { cout<<"表达式 有错"< 0; }// “(”放表达式最后 面，错误 if(line[i]=='-' || line[i]=='+' || line[i]=='*' || line[i]=='/' || line[i]=='^') { if(i==len) { cout<<"表达 式有错"< 0; }//“+、-、*、/、^” 放在表达式最后面，错误 if( (!isdigit(line[i+1])) && (!isalpha(line[i+1])) && line[i+1]!='(')//“+、 -、*、/、^”后面跟的不是 数字或者变量，错误 { cout<<"表达式有错 "< } if(line[i]=='-' && (i==0 || line[i-1]=='(' ))//运 算符是负号 { push(stack1,0); push2(stack2,line[i]); i++; } else { //读入的运算符与运算符 栈的栈顶元素相比，并进行 相应的操作 if(in[]) stackempty2(stack2)) { push2(stack2,line[i]) ;i++;} else if(in[])==out(line[i])) {i++; ;} else if(in[])>out(line[i])) { pop(stack1,a); pop(stack1,b); pop2(stack2,operate); count(b,operate,a); } if(i>=len) break; } } else { if(isalpha(line[i]))// 读入的字符是字母变量的 情况 { g=1; cout<<"请输入变量"; while( isalpha(line[i])) { cout< cout<<"的值"< cin>>b; push(stack1,b); if(i>=len) break; if(line[i]!='-' && line[i]!='+' && line[i]!='*' && line[i]!='/' && line[i]!='^' && line[i]!=')')//变量后面 跟的不是“+、-、*、/、^、)”， 则为错误 { cout<<"表达式有错 "< } } } if(g==0) { cout<<"表达式 有错"< 0; }//g=0表示该字符是不 符合要求的字符 } while!=-1)//读入结束后， 继续进行操作，直到运算符 栈为空 { pop(stack1,a); pop(stack1,b); pop2(stack2,operate); if(operate=='(' || operate==')') //括号多余 的情况 { cout<<"表达式有错 "< count(b,operate,a); } cout<<[]< return 0; } 整型数运行结果如下： 浮点数运行结果如下： 八、思考题 1、如何实现前缀算术表达式、后缀表达式的求解 答：用栈来实现表达式的中缀表示法变后缀要用一个字符型数组OPTR作为栈，存放括号和运算符。设字符“#”为表达式的终止符，方法如下： 先将一个左括号“（”压入栈OPTR，作为栈底元素，输入时以“#”作为输入的结束标 志。 依次读入表达式中的字符，对于每一个字符有三种情况： 第一种情况是——数字；处理方式：将字符直接赋值到后缀表达式串中。 第二种情况是——非数字非运算符；处理方式：结束。 第三种情况是——运算符；处理情况按运算符与栈顶运算符的三种优先关系； ①大于栈顶优先级：将字符直接赋值到后缀表达式串中。 ②等于栈顶优先级：将栈顶元素退栈，处理表达式中下一个字符。 ③小于栈顶优先级：将栈顶元素退栈，并将推出栈的元素输出到后缀表示式串中int transExpression(char *str1,char *str2) { /*将中缀表达式串str1，转换为后缀表达式str2*/ IniStack(OPTR); Push(OPTR, ′#′)； i=0;k=0; whi le(str1[i]!=′#′||GetTop(OPTR )!=′#′) {if(str1[i]>=′0′&&c<=′9′) str2[k++]=str1[i++]； /*数复制到 str2中*/ else { if judge(str1[i]) return ERROR; /* 判断是否操作符，若不是结束*/ switch(Precede(GetTop(OPTR),str[i ]) /*比较操作符优先级高低*/ { case ′<′： /*栈顶优先级时str1[i]低直接复制到str2[k]中*/ str2[k++]=str1[i++]； break；case ′=′： /*优先级相等脱括号并处理下一个字符*/ Pop(OPTR,x)；i++； break； case ′>′： /*栈顶优先级高，将栈顶复制到str2中*/ Pop(OPTR,theta)； str2[k++]=theta; break； } } } return OK； /*正确返回*/ } ,