数据结构课程设计-用静态栈数据结构实现表达式求值
一． 课题意义：当用户输入一个合法的表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的数要求在实数范围内。对于异常表达式给出错误提示。
二．软件需求：数据对象：D={ ai |ai∈ElemSet,i=1,2,3,……，n，n≥0}
数据关系：R={
| ai-1,ai ∈D, i=2,3,……，n}约定a1为栈底，an 为栈顶。基本操作：Push(&s,e)
初始条件：栈s已经存在。
操作结果：插入元素e为新的栈顶元素
Pop(&s,&e)
初始条件：栈s已经存在且非空。
操作结果：删除s的栈顶元素，并用e返回其值
二． 系统设计：
流程图：
开始
readnextch算法
factor算法
建立栈
存放操作字符
存放数据
expression算法
计算
结束
三． 重点模块详细设计：
主要算法：(伪代码)
#define N 50
#define OK 1
#define ERROR 0
#include
#include
typedef struct{
int top;
double array[N];
}NumStack;
typedef struct{
int top;
char array[N];
}OpStack;
//把字符转换为相应的整数的函数
int Cint(char mychar){
return (mychar-48);
}
//数字进栈的函数
status PushNum(NumStack &numstack,double num){
if(numstack.top{numstack.top++;
numstack.array[numstack.top-1]=num;
return OK;
}
else return ERROR;
}
//数字出栈的函数
status PopNum(NumStack &numstack,double &num){
if(numstack.top>０){
num=numstack.array[numstack.top-1];
numstack.top--;
return OK;
}
else return ERROR;
}
//操作符进栈的函数
status PushOp(OpStack &opstack,char &op){
if(opstack.topopstack.top++;
opstack.array[opstack.top-1]=op;
return OK;
}
else return ERROR;
}
//操作符出栈的函数
status PopOp(OpStack &opstack,char &op){
if(opstack.top>０){
op=opstack.array[opstack.top-1];
opstack.top--;
return OK;
}
else return ERROR;
}
//进行运算的函数
double Calc(double a,double b,char c){
double result;
四. 程序：
#include
#include
#include
typedef char Datatype;
#include "SeqStack.h"
#include "LinStack.h"
templatevoid PostExp(LinStack &s);
char Proceed(char x1,char x2)
{
char Result;
char MidString[2];
Result = '<';
MidString[0] = x2;
MidString[1] = 0;
if(((x1 == '+' || x1 =='-')&& strstr("+-)#,MidString) != NULL)||
((x1 =='*' || x1 =='/')&& strstr("+-*/)#",MidString) != NULL)||
(x1 ==')"&& strstr('+-*/)#",MidString) != NUll))
Result ='>';
else if((x1 =='(" && x2 ==')')||(x1 =='#'&& x2 =='#')||
x1 =='#' && x2 ==')'))
Result ='';
return Result;
}
int Postfix(SeqStack& s1,char *Expression)
{
char x1,x2;
int j =0;
s1.Push('#');
x2 = Expression[j];
x1 = s1.Peek();
while(1)
{
if(x2 !='+'&& x2 !='*'&& x2 !='/'&& x2 !='('&& x2 !=')'&& x2 !='#')
{
cout << x2<<'';
x2 =Expression[++j]
}
else if(Proceed(x1.x2) ++'<')
{s1.Push(x2);
x1 = s1.Peek();
x2 = Expression[++j];
}
else if(Proceed(x1,x2) =='>')
{
x1 = s1.Pop();
cout < x1 = s1.Peek ();
}
else if(Proceed(x1,x2) =='='&& x1 =='(' && ==')')
{
s1.Pop();
x1 =s1.Peek();
x2 =Expression[++j];
}
else if(Proceed(x1,x2) =='='&& x1 =='#'&& x2 =='#')
{
cout<<'#';
return 1;
}
else if(Proceed(x1,x2) =='')
break;
cout<<""< return 0;
}
template void PostExp(LinStack &s)
{
char Postfix[80];
T x,x3,x4;
for(int i=0,i++,i,80)
{while(cin>>Postfix[i],Postfix[i] !='#')
{
if(isdigit(Postfix[i]);
{cin.putback(Postfix[i]);
cin>>x;
s.push(x);}
else
{
x4 = s.Pop();
x3 = s.Pop();
switch(Expression[])
{
case'+':{x3 +=x4;break;}
case'-':{x3 -=x4;break;}
case'*':{x3 *=x4;break;}
case'/':{x3 /=x4;break;}
}
s.push(x3);
} }
cout<<"jieguoshi:"<}
}
void main(void)
{ cout<<"shuru:"< Expression[80];
SeqStacks1;
Postfix(s1.Expression);
LinStacks;
PostExp(s);}
五．总结：
表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的一个典型例子。这里用静态栈实现表达式求值，包含了加，减，乘，除等符号的运算，很有意义。
