数据结构课程设计-表达式求值问题.doc

(完整word版)数据结构课程设计-表达式求值问题
实验 表达式求值问题

1.问题描述
表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3.中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀表达式（如：11 22 7 4 - * 3 / +）和前缀表达式（+ 11 / * 22 - 7 4 3）。后缀表达式
和前缀表达式中没有括号，给计算带来方便。如后缀表达式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。
2.数据结构设计
（1）顺序栈类定义：首先应在类中定义成员函数，以此来完成顺序栈的相关操作，如下：
class SqStack
{
private:
T *base; //栈底指针
int top; //栈顶
int stacksize; //栈容量
public:
SqStack(int m); //构建函数
~SqStack(){delete [] base;top=0;stacksize=0;} //析构函数
void Push(T x); //入栈
T Pop(); //出栈
T GetTop(); //获取栈顶元素
int StackEmpty(); //测栈空
void ClearStack(); //清空栈
void StackTop(); //返回栈顶指针
void StackTranverse(); //显示栈中元素
};
（2）顺序栈类实现：对顺序栈进行初始化，初始化的首要操作就是创建一个空顺序栈。
Step1：申请一组连续的内存空间为顺序栈使用：
base=new T[m];
if(base==NULL)
{
cout<<"栈创建失败，退出!"<<endl;
exit(1);
}
Step2：给栈顶、栈容量赋相应的值：
stacksize=m;
top=-1;
（2）顺序栈入栈：入栈需要在栈顶插入一个新元素并相应的调整栈顶。
Step1：首先判断是否栈满，如果栈满，抛出“上溢”信息，无法入栈，否则转入Step2；
if(top==stacksize-1) throw "栈满，无法入栈";
Step2：栈顶指针增加1；
top++;
Step3：新元素插入栈顶位置；
base[top]=x;
（3）顺序栈出栈：出栈需要取出栈顶元素，并相应的调整栈顶指针。
Step1：首先判断是否栈空，如果栈空，抛出“下溢”信息，无法出栈，否则转入Step2；
if(top==-1) throw "栈空，不能出栈";
Step2：取出栈顶元素，栈顶指针减1；
T x;
x=base[top--];
Step3：返回栈顶元素；
return x；
（4）顺序栈取栈顶元素：取栈顶元素是取出栈顶元素的值，但不改变栈。
Step1：首先判断是否栈空，如果栈空，抛出“下溢”信息，无法出栈，否则转入Step2；
if(top==-1) throw "栈空，栈顶无元素";
Step2：取出栈顶元素，返回栈顶元素；
return base[top];
（5） 判断栈空：判断是否栈空，返回
Step1：如果栈空，返回1，否则转Step2；
if(top==-1)
return 1;
Step2：否则返回0；
return 0;
（6） 清空栈：将栈清空。
top=-1
（7） 返回栈顶指针：
cout<<"栈顶top= "<<top;
（8） 输出栈元素：将栈顶指向i，从栈顶输出到栈底。
Step1：将栈顶指针赋予i；
int i=top;
Step2：如果栈不为空，则输出；
while(i>=0)
cout<<base[i--]<<'\t';
cout<<endl;
3. 算法设计
本实验要求读入中缀表达式，求中缀表达式，将中缀表达式转换成前，后缀表达式，利用前，中，后缀表达式求值，并且能够输出等等操作，这就需要构建相关算法。
（1） 首先要将表达式中操作符优先级进行排序，优先级从高到低依次为（，），*，/，+，-，算法如下，利用选择语句比较：
char Precede(char t1,char t2)
{//运算符的优先级比较
char f;
switch(t2)
{
case '+':
case '-':if(t1=='('||t1=='=')
f='<';
else
f='>';
break;
case '*':
case '/':if(t1=='*'||t1=='/'||t1==')')
f='>';
else
f='<';
break;
case '(':if(t1==')')
{
cout<<"ERROR1"<<endl;
exit(0);
}
else
f='<';
break;
case ')':switch(t1)
{
case '(':f='=';
break;
case '=':cout<<"ERROR2"<<endl;
exit(0);
default: f='>';
}
break;
case '=':switch(t1)
{
case '=':f='=';
break;
case '(':cout<<"ERROR2"<<endl;
exit(0);
default: f='>';
}
}
return f;
}
（2） 其次，就是判断输入元素是否为运算符，若为运算符，就输出1，否则输出0；
int In(char c)
{ // 判断c是否为运算符
switch(c)
{
case'+':
case'-':
case'*':
case'/':
case'(':
case')':
case'=':return 1;
default:return 0;
}
}
（3） 构造表达式的运算算法，利用选择语句将运算分类：
float Operate(float a,char theta,float b)
{//实施一次运算
float c;
switch(theta)
{
case'+':c=a+b;
break;
case'-':c=a-b;
break;
case'*':c=a*b;
break;
case'/':c=a/b;
}
return c;
}
（4） 要求一：中缀表达式求值
Step1：首先需要将运算符和运算数分开存放，这就需要分别创建栈：
SqStack<char> OP(20);
SqStack<float> OD(20);
Step2:创建相关字符来存放由键盘输入的字符，并以“=”键结束
char theta;
float a,b,d;
char c,x; // 存放由键盘接收的字符
char z[6]; // 存放符点数字符串
int i;
OP.Push('=');
Step3：当输入为数字元素是，直接存入表达式栈就可以，而当输入是符号元素时，就需要判断优先级并进行存栈出栈操作，如果是非法字符，输出错误，并且不存入；
c=*exp++;
x=OP.GetTop();
while(c!='='||x!='=')
{
if(In(c)) // 是7种运算符之一
switch(Precede(x,c))
{
case'<':OP.Push(c); // 栈顶元素优先权低
c=*exp++;
break;
case'=':x=OP.Pop(); // 脱括号并接收下一字符
c=*exp++;
break;
case'>':theta=OP.Pop(); // 退栈并将运算结果入栈
b=OD.Pop();
a=OD.Pop();
OD.Push(Operate(a,theta,b));
}
else if(c>='0'&&c<='9'||c=='.') // c是操作数
{
i=0;
do
{
z[i]=c;
i++;
c=*exp++;
}while(c>='0'&&c<='9'||c=='.');
z[i]='\0';
d=atof(z); // 将字符串数组转为符点型存于d
OD.Push(d);
}
else // c是非法字符
{
cout<<"ERROR3"<<endl;;
exit(0);
}
x=OP.GetTop();
}
d=OD.GetTop();
return d;
}

（4）中缀表达式转换成后缀表达式：
Step1：创建一个操作符栈；
char c,x;
int i=0;
SqStack<char> OP(20);
Step2：从左到右扫描读取表达式，执行下列运算，直至表达式结束符。
SqStack<char> OP(20);
OP.Push('='); // =是表达式结束标志
cout<<"exp:"<<exp<<endl;
c=*exp++;
2.1：如果是操作数，输出；
if((c>='0'&&c<='9')||c=='.')
{
postexp[i++]=c;
c=*exp++;
}
2.2：如果是操作符A2，把操作符栈栈顶的操作符A2与它比较：
2.2.1：A1<A2，A2如操作符栈。
2.2.2：A1=A2，从操作符栈退出一个操作符，不输出。
2.2.3：A1>A2，从操作符栈输出所有比A2优先级高的运算符，直至栈顶算符优先级小于A2，A2如操作符栈。
if(In(c)) // 是7种运算符之一
{
postexp[i++]=' ';
x=OP.GetTop();
switch(Precede(x,c))
{
case'<':OP.Push(c); // 栈顶元素优先权低
c=*exp++;
break;
case'=':x=OP.Pop(); // 脱括号并接收下一字符
c=*exp++;
break;
case'>':postexp[i++]=OP.Pop(); // 运算符出栈输出
break;
}
}
postexp[i]='\0';
（4）中缀表达式转换成前缀表达式：
Step1：创建一个操作符栈；
char c,x;
int i=0;
SqStack<char> OP(20);
Step2：从右到左扫描读取表达式，执行下列运算，直至表达式结束符；
while(*exp != '\0')
*exp++;
OP.Push('='); // =是表达式结束标志
c=*exp--;
2.1：如果是操作数，输出；
if((c>='0'&&c<='9')||c=='.')
{
preexp[i++]=c;
c=*exp--;
}
2.2：如果是操作符A2，把操作符栈栈顶的操作符A2与它比较：
2.2.1：A1<A2，A2如操作符栈。
2.2.2：A1=A2，从操作符栈退出一个操作符，不输出。
2.2.3：A1>A2，从操作符栈输出所有比A2优先级高的运算符，直至栈顶算符优先级小于A2，A2如操作符栈。
if(In(c)) // 是7种运算符之一
{
preexp[i++]=' ';
x=OP.GetTop();
switch(Precede(x,c))
{
case'<':OP.Push(c); // 栈顶元素优先权低
c=*exp--;
break;
case'=':x=OP.Pop(); // 脱括号并接收下一字符
c=*exp--;
break;
case'>':preexp[i++]=OP.Pop(); // 运算符出栈输出
break;
}
}
preexp[i]='\0';
}//while
（5）后缀表达式求值：
Step1：创建一个栈，作为操作数栈；
SqStack<float> OD(20);
Step2：执行下列操作，直到表达式结束；
2.1：读取表达式：
c=*postexp++;
2.2：如果是操作数，入操作数栈；
if((c>='0'&&c<='9')||c=='.')//为操作数
{
i=0;
do
{
z[i++]=c;
c=*postexp++;
}while(c>='0'&&c<='9'||c=='.');
z[i]='\0';
d=atof(z); // 将字符串数组转为符点型存于d
OD.Push(d);
}
2.3如果是操作符A，从操作数栈推出两个操作数a，b，进行运算。并把运算结果入操作数栈；
if(In(c))//c为运算符
{
b=OD.Pop ();
a=OD.Pop ();
OD.Push (Operate(a,c,b));
c=*postexp++;
}
c=*postexp++;
}
Step3：栈顶元素即为表达式的值，返回它；
v=OD.Pop ();
return v;
（6）前缀表达式求值；
Step1：创建一个栈，作为操作数栈；
SqStack<float> OD(20);
Step2：执行下列操作，直到表达式结束；
2.1：读取表达式：
c=*preexp--;
2.2：如果是操作数，入操作数栈；
if((c>='0'&&c<='9')||c=='.')//为操作数
{
i=0;
do
{
z[i++]=c;
c=*preexp--;
}while(c>='0'&&c<='9'||c=='.');
z[i]='\0';
d=atof(z); // 将字符串数组转为符点型存于d
OD.Push(d);
}
2.3如果是操作符A，从操作数栈推出两个操作数a，b，进行运算。并把运算结果入操作数栈；
if(In(c))//c为运算符
{
b=OD.Pop ();
a=OD.Pop ();
OD.Push (Operate(a,c,b));
c=*preexp--;
}
c=*preexp--;
}
Step3：栈顶元素即为表达式的值，返回它；
v=OD.Pop ();
return v;
（7）界面设计：
界面要求简洁明了，能够方便用户进行功能选择，菜单界面如下：
1-创建表达式
2-表达式求值
3-求后缀表达式
4-后缀表达式求值
5-求前缀表达式
6-前缀表达式求值
7-显示表达式
8-退出
4.运行与测试
（1）运行程序，显示菜单，如图所示：

（2）创建表达式，由中前后缀表达式计算结果如下图所示：

（3）将中缀表达式转化为前后缀表达式：

5.调试记录及收获
本次试验为表达式求值实验，首先需要对表达式进行输入存入处理，这就需要利用栈的特性，中缀表达式和中转后都比较容易写出，就是中转前需要将表达式从后往前遍历，这就需要将指针先移到字符串的尾端，我这里运用了while(*exp != '\0')
*exp++;的代码，将exp移到最后，，从右往左对c赋值，然后进行比较。此时得到的前缀表达式就是3 4 7 – 2 * / 1 + ，此时利用栈的特性，后进先出，将栈顶元素先行压出，这就反转成了前缀表达式 + 1 / * 2 – 7 4 3 ，此时就大功告成了。
本次试验中，实现了表达式的求值和中缀表达式转换成前后缀表达式，更重要的是，我理解了栈的使用方法以及指针的运用方式。
附录：程序清单：
头文件：
//顺序栈类定义
template <class T>
class SqStack
{
private:
T *base;//栈底指针
int top;//栈顶
int stacksize;//栈容量
public:
SqStack(int m);//构建函数
~SqStack(){delete [] base;top=0;stacksize=0;}//析构函数
void Push(T x);//入栈
T Pop();//出栈
T GetTop();//获取栈顶元素
int StackEmpty();//测栈空
void ClearStack();//清空栈
void StackTop();//返回栈顶指针
void StackTranverse();//显示栈中元素
};
//顺序栈类实现
template <class T>
SqStack<T>::SqStack(int m)
{

base=new T[m];
if(base==NULL)
{
cout<<"栈创建失败，退出!"<<endl;
exit(1);
}
stacksize=m;
top=-1;
}

template <class T>
void SqStack<T>::Push(T x)
{
if(top==stacksize-1) throw "栈满，无法入栈";
top++;
base[top]=x;
//cout<<"top："<<top<<endl;
}

template <class T>
T SqStack<T>::Pop()
{
T x;
if(top==-1) throw "栈空，不能出栈";
x=base[top--];
//cout<<"top："<<top<<endl;
return x;
}

template <class T>
T SqStack<T>::GetTop()
{
if(top==-1) throw "栈空，栈顶无元素";
//cout<<"top："<<top<<endl;
return base[top];
}

template <class T>
int SqStack<T>::StackEmpty()
{
if(top==-1)
return 1;
else
return 0;
}

template <class T>
void SqStack<T>::ClearStack()
{
top=-1;
}

template <class T>
void SqStack<T>::StackTop()
{//返回栈顶指针
cout<<"栈顶top= "<<top;
}

template <class T>
void SqStack<T>::StackTranverse()
{
int i=top;
while(i>=0)
cout<<base[i--]<<'\t';
cout<<endl;
}

主函数：
#include<iostream.h>//cout,cin
#include"process.h"//exit()
#include"stdio.h"//EOF,NULL
#include<string.h>
#include<stdlib.h> // atoi()
#include"SqStack.h"
char pause;

char Precede(char t1,char t2)
{//算符的优先级比较
char f;
switch(t2)
{
case '+':
case '-':if(t1=='('||t1=='=')
f='<';
else
f='>';
break;
case '*':
case '/':if(t1=='*'||t1=='/'||t1==')')
f='>';
else
f='<';
break;
case '(':if(t1==')')
{
cout<<"ERROR1"<<endl;
exit(0);
}
else
f='<';
break;
case ')':switch(t1)
{
case '(':f='=';
break;
case '=':cout<<"ERROR2"<<endl;
exit(0);
default: f='>';
}
break;
case '=':switch(t1)
{
case '=':f='=';
break;
case '(':cout<<"ERROR2"<<endl;
exit(0);
default: f='>';
}
}
return f;
}

int In(char c)
{ // 判断c是否为运算符
switch(c)
{
case'+':
case'-':
case'*':
case'/':
case'(':
case')':
case'=':return 1;
default:return 0;
}
}

float Operate(float a,char theta,float b)
{//实施一次运算
float c;
switch(theta)
{
case'+':c=a+b;
break;
case'-':c=a-b;
break;
case'*':c=a*b;
break;
case'/':c=a/b;
}
return c;
}

float Val_Exp(char *exp)
{ //中缀表达式求值。设OPTR和OPND分别为运算符栈和运算数栈
SqStack<char> OP(20);
SqStack<float> OD(20);
char theta;
float a,b,d;
char c,x; // 存放由键盘接收的字符
char z[6]; // 存放符点数字符串
int i;
OP.Push('='); // =是表达式结束标志
c=*exp++;
x=OP.GetTop();
while(c!='='||x!='=')
{
if(In(c)) // 是7种运算符之一
switch(Precede(x,c))
{
case'<':OP.Push(c); // 栈顶元素优先权低
c=*exp++;
break;
case'=':x=OP.Pop(); // 脱括号并接收下一字符
c=*exp++;
break;
case'>':theta=OP.Pop(); // 退栈并将运算结果入栈
b=OD.Pop();
a=OD.Pop();
OD.Push(Operate(a,theta,b));
}
else if(c>='0'&&c<='9'||c=='.') // c是操作数
{
i=0;
do
{
z[i]=c;
i++;
c=*exp++;
}while(c>='0'&&c<='9'||c=='.');
z[i]='\0';
d=atof(z); // 将字符串数组转为符点型存于d
OD.Push(d);
}
else // c是非法字符
{
cout<<"ERROR3"<<endl;;
exit(0);
}
x=OP.GetTop();
}
d=OD.GetTop();
return d;
}

void CreatePostExp(char * exp,char * &postexp)
{//由中缀式求后缀式
char c,x;
int i=0;
SqStack<char> OP(20);
OP.Push('='); // =是表达式结束标志
cout<<"exp:"<<exp<<endl;
c=*exp++;
while(c)
{
if((c>='0'&&c<='9')||c=='.')
{
postexp[i++]=c;
c=*exp++;
}
if(In(c)) // 是7种运算符之一
{
postexp[i++]=' ';
x=OP.GetTop();
switch(Precede(x,c))
{
case'<':OP.Push(c); // 栈顶元素优先权低
c=*exp++;
break;
case'=':x=OP.Pop(); // 脱括号并接收下一字符
c=*exp++;
break;
case'>':postexp[i++]=OP.Pop(); // 运算符出栈输出
break;
}
}
postexp[i]='\0';
}//while
cout<<"后缀表达式为:"<<postexp<<endl;
}

void CreatePre(char * exp,char * &preexp)
{//由中缀式求前缀式
char c,x;
int i=0;
SqStack<char> OP(20);
cout<<"exp:"<<exp<<endl;
while(*exp != '\0')
*exp++;
OP.Push('='); // =是表达式结束标志
c=*exp--;
while(c)
{
if((c>='0'&&c<='9')||c=='.')
{
preexp[i++]=c;
c=*exp--;
}
if(In(c)) // 是7种运算符之一
{
preexp[i++]=' ';
x=OP.GetTop();
switch(Precede(x,c))
{
case'<':OP.Push(c); // 栈顶元素优先权低
c=*exp--;
break;
case'=':x=OP.Pop(); // 脱括号并接收下一字符
c=*exp--;
break;
case'>':preexp[i++]=OP.Pop(); // 运算符出栈输出
break;
}
}
preexp[i]='\0';
}//while
cout<<"前缀表达式为:"<<preexp[i--]<<endl;
}

float Val_PostExp(char *postexp)
{//后缀表达式求值
int i;
char z[6];
float v=0,d=0,a,b;
char c;
SqStack<float> OD(20);
c=*postexp++;
while(c!='\0')
{
if((c>='0'&&c<='9')||c=='.')//为操作数
{
i=0;
do
{
z[i++]=c;
c=*postexp++;
}while(c>='0'&&c<='9'||c=='.');
z[i]='\0';
d=atof(z); // 将字符串数组转为符点型存于d
OD.Push(d);
}
if(In(c))//c为运算符
{
b=OD.Pop ();
a=OD.Pop ();
OD.Push (Operate(a,c,b));
c=*postexp++;
}
c=*postexp++;
}
v=OD.Pop ();
return v;
}

float Val_PreExp(char *preexp)
{//前缀表达式求值
int i;
char z[6