用静态栈数据结构实现表达式求值
一、题目：
当用户输入一个合法的表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的数要求在实数范围内。对于异常表达式给出错误提示。（要求使用静态栈数据结构。）
二、数据结构：
数据对象：D={ ai |ai∈ElemSet,i=1,2,3,……，n，n≥0}
数据关系：R={<ai-1,ai,)>| ai-1,ai ∈D, i=2,3,……，n}
约定a1为栈底，an 为栈顶。
基本操作：
Push(&s,e)
初始条件：栈s已经存在。
操作结果：插入元素e为新的栈顶元素
Pop(&s,&e)
初始条件：栈s已经存在且非空。
操作结果：删除s的栈顶元素，并用e返回其值
.
.
.
三、存储结构：
typedef struct{
Array[N-1]
……
Array[0]
Top
……
int top;
double array[N];
}NumStack; //存放实数的栈
typedef struct{
int top;
char array[N];
}OpStack; //存放操作符的栈
四、主要算法：(伪代码)
#define N 50
#define OK 1
#define ERROR 0
#include <ctype.h>
#include <string.h>
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<N)
{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.top<N){
opstack.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;
switch(c){
case '+':result=a+b;
break;
case '-':result=a-b;
break;
case '*':result=a*b;
break;
case '/':result=a/b;
break;
}
return result;
}
//判断优先级的函数
char Priority(char y,char x){
char priority='<';
switch(x){
case '+':
case '-':if(y=='(' || y=='#')priority='>';
break;
case '*':
case '/':if(y=='(' || y=='#'|| y=='+' || y=='-')priority='>';
break;
case '(':priority='>';
break;
case ')':if(y=='(')priority='=';
break;
case '#':if(y=='#')priority='=';
break;
default:priority='E';
}
return priority;
}
//处理表达式的主体函数
void Process(NumStack &numstack,OpStack &opstack,char x){
double a,b;char c;
static double tempnum=0.00000000;static int len=10;static int dot=0,flags=0;
if(isdigit(x) || x=='.'){
if(x=='.')dot=1;
else{
if(dot==0)
tempnum=tempnum*10+Cint(x);
else{
tempnum=tempnum+(double)Cint(x)/len;
len*=10;
}
}
}
else{
if(flags==0 && x!='('){PushNum(numstack,tempnum);tempnum=0.00000000;len=10;dot=0;}
switch(Priority(opstack.array[opstack.top-1],x)){
case '>':PushOp(opstack,x);flags=0;
break;
case '<':
PopOp(opstack,&c);
PopNum(numstack,&b);
PopNum(numstack,&a);
PushNum(numstack,Calc(a,b,c));flags=1;
Process(numstack,opstack,x);
break;
case '=':PopOp(opstack,&c);flags=1;
break;
default:printf("Wrong Express!");exit(0);
}
}
}
//main函数
main(){
NumStack numstack;OpStack opstack;char *s;int i=0;
numstack.top=0;opstack.top=0;
PushOp(&opstack,'#');
printf("\nEnter your expression adn end it with #:");scanf("%s",s);
for(i=0;i<strlen(s);i++)
Process(&numstack,&opstack,s[i]);
printf("The result is %f",numstack.array[numstack.top-1]);
}
五、测试数据:
ignore....
六、小结：
这次实验难度较高，我做了几个版本。最初的一个版本由于只用了一个栈，导致不能算小数。第二个版本用的是输入一次处理一次，不能处理括号运算。这一个版本，我个人目前比较满意。代码只有９２行，但是功能很完善，能够处理实数的加减乘除运算，乘除法运算无误差，能执行多重括号嵌套运算。并且对错误表达式也有一定的识别能力。
附C语言的源代码:
#define N 50
#include <ctype.h>
#include <string.h>
typedef struct{
int top;
double array[N];
}NumStack;
typedef struct{
int top;
char array[N];
}OpStack;
int Cint(char mychar){
return (mychar-48);
}
void PushNum(NumStack *numstack,double num){
numstack->top++;
numstack->array[numstack->top-1]=num;
}
void PopNum(NumStack *numstack,double *num){
*num=numstack->array[numstack->top-1];
numstack->top--;
}
void PushOp(OpStack *opstack,char op){
opstack->top++;
opstack->array[opstack->top-1]=op;
}
void PopOp(OpStack *opstack,char *op){
*op=opstack->array[opstack->top-1];
opstack->top--;
}
double Calc(double a,double b,char c){
double result;
switch(c){
case '+':result=a+b;break;
case '-':result=a-b;break;
case '*':result=a*b;break;
case '/':result=a/b;break;
}
return result;
}
char Priority(char y,char x){
char priority='<';
switch(x){
case '+':
case '-':if(y=='(' || y=='#')priority='>';break;
case '*':
case '/':if(y=='(' || y=='#'|| y=='+' || y=='-')priority='>';break;
case '(':priority='>';break;
case ')':if(y=='(')priority='=';break;
case '#':if(y=='#')priority='=';break;
default:priority='E';
}
return priority;
}
void Process(NumStack *numstack,OpStack *opstack,char x){
double a,b;char c;
static double tempnum=0.00000000;static int len=10;static int dot=0,flags=0;
if(isdigit(x) || x=='.'){
if(x=='.')dot=1;
else{
if(dot==0)
tempnum=tempnum*10+Cint(x);
else{
tempnum=tempnum+(double)Cint(x)/len;
len*=10;
}
}
}
else{
if(flags==0 && x!='('){PushNum(numstack,tempnum);tempnum=0.00000000;len=10;dot=0;}
switch(Priority(opstack->array[opstack->top-1],x)){
case '>':PushOp(opstack,x);flags=0;break;
case '<':
PopOp(opstack,&c);
PopNum(numstack,&b);
PopNum(numstack,&a);
PushNum(numstack,Calc(a,b,c));flags=1;
Process(numstack,opstack,x);break;
case '=':PopOp(opstack,&c);flags=1;break;
default:printf("Wrong Express!");exit(0);
}
}
}
main(){
NumStack numstack;OpStack opstack;char s[N];int i=0;
numstack.top=0;opstack.top=0;
PushOp(&opstack,'#');
printf("\nEnter your expression and end it with #:");scanf("%s",s);
for(i=0;i<strlen(s);i++)
Process(&numstack,&opstack,s[i]);
printf("The result is %f",numstack.array[numstack.top-1]);
}