《数据结构（C++版）》课设计报告2012—2013学年第一学期
课程名称数据结构
设计题目表达式求值
专业班级
姓名
学号
指导教师
课程设计题目：表达式求值
一、问题描述
对一个合法的中缀表达式求值。简单起见，假设表达式只包含+，-，*，/等4个双目运算符，且运算符本身不具有二义性，操作数均为一位整数。
二、基本要求
1.正确解释表达式；
2.符合四则运算规则；
3.输出最后的计算结果。
三、概要设计
对中缀表达式求值，通常使用“算符优先算法”。根据四则运算规则，在运算的每一步中，任意两个相继出现的运算符t和c之间的优先关系至多是下面三种关系之一：
（1） t的优先级低于c；
（2） t的优先级等于c；
（3） t的优先级高于c。
为实现算符优先算法，可以使用两个工作栈：一个栈OPTR存放运算符；另一个栈OPND存放操作数，中缀表达式用一个字符串数组存储。
四、详细设计
利用类模板
#include
using namespace std;
const int StackSize=100;
template //定义模板类SeqStack
class SeqStack{
public:
SeqStack( ) ; //构造函数，栈的初始化
~SeqStack( ); //析构函数
void Push(DataType x); //将元素x入栈
DataType Pop( ); //将栈顶元素弹出
DataType GetTop( ); //取栈顶元素（并不删除）
int Empty( ); //判断栈是否为空
void Printf();
private:
DataType data[StackSize]; //存放栈元素的数组
int top; //栈顶指针，指示栈顶元素在数组中的下标
};
template
SeqStack::SeqStack( ){ top=-1; }
template
SeqStack::~SeqStack( ){}
template
void SeqStack::Push(DataType x){ if (top==StackSize-1) throw "上溢";
data[++top]=x;
}
template
DataType SeqStack::Pop( ){ DataType x;
if (top==-1) throw "下溢";
x=data[top--];
return x;
}
template
DataType SeqStack::GetTop( ){
if (top!=-1)
return data[top];
}
template
int SeqStack::Empty( ){
if(top==-1) return 1;
else return 0;
}
template
void SeqStack::Printf(){
while(top!=-1)
{
cout<Pop();
}
}
int isp(char op){
switch(op){
case '\0':
return 0;
break;
case '+':
return 3;
break;
case '-':
return 3;
break;
case '*':
return 5;
break;
case '/':
return 5;
break;
case '(':
return 1;
break;
default:
return 6;
}
}
int icp(char ch){ switch(ch){
case '+':
return 2;
break;
case '-':
return 2;
break;
case '*':
return 4;
break;
case '/':
return 4;
break;
case '(':
return 6;
break;
case ')':
return 1;
break;
default:
return 0;
}
}
