计算表达式的值--顺序栈

63 阅读 0 评论 42 点赞

我是靠谱客的博主懵懂微笑，最近开发中收集的这篇文章主要介绍计算表达式的值--顺序栈，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

实验题目：栈的应用－算术表达式求值

实验环境： Visual C++ 6.0 　

实验目的：

1 ．掌握栈的定义及实现；

2 ．掌握利用栈求解算术表达式的方法。

实验内容：

通过修改完善教材中的算法3.4，利用栈来实现算术表达式求值的算法。对算法3.4中调用的几个函数要给出其实现过程：

(1) 函数In(c)：判断c是否为运算符；

(2) 函数Precede(t1,t2)：判断运算符t1和t2的优先级；

(3) 函数Operate(a,theta,b)：对a和b进行二元运算theta。

程序运行时，输入合法的算术表达式（中间值及最终结果要在0～9之间，可以包括加减乘除和括号），便可输出相应的计算结果。如下图：

实验提示：（仅供参考，每个函数的具体实现可以有多种方法，希望有创新）

1. 将栈的定义和实现单独保存在头文件“stack.h”中，然后在表达式求值的源程序中包含此头文件（即#include“stack.h”）。

2. 表达式求值源程序的具体实现

(1) 主函数如下：

void main()

{

Printf(“ 请输入算术表达式,并以#结束.n”);

Printf(“the result of expression is:%dn”,EvaluateExpression());

}

(2) 函数EvaluateExpression的实现见算法3.22

(3) 函数In(c)的实现可以采用以下方式：

Status In(SElemType c)// 应在前面有定义typedef char SElemType;

{ // 判断c是否为运算符

switch(c)

{

case'+':return TRUE;

……// 补充完整

default:return FALSE;

}

(4) 函数Precede(t1,t2)的实现可以采用以下形式：

SElemType Precede(SElemType t1,SElemType t2)

{ // 根据教材表3.1，判断两个运算符的优先关系

SElemType f;

switch(t2)

{

case '+':

case '-':if(t1=='('||t1=='#')

f='<';

else

f='>';

break;

……// 补充完整

}

return f;

}

(5) 函数Operate(a,theta,b)的实现可以采用以下方式：

SElemType Operate(SElemType a,SElemType theta,SElemType b)

{

SElemType c;

a=a-48;

b=b-48;

switch(theta)

{

case'+':c=a+b+48;

break;

……// 补充完整

}

return c;

}

选做内容： 进一步改进，使表达式的中间值及最终结果不局限于0～9之间的个位数。（如果完成要在实验报告中注明），如下图：

实验要求：

(1) 程序要添加适当的注释，程序的书写要采用缩进格式。

(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。

(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

(4) 根据实验报告模板详细书写实验报告,在实验报告中给出表达式求值算法的流程图。

(5) 上传源程序到Sakai网络教学平台。顺序表的源程序保存为 calculator.c 。

#include<stdio.h>
#include<string.h>
#include<stdlib.h> 
#include<malloc.h>
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define MAXSIZE 100 
typedef int Status;
typedef char SElemType;
//存储结构
 typedef struct
 {
 	SElemType *base;//栈底指针
	 SElemType *top;//栈顶指针
	 int stacksize;//栈可用最大容量 
 }SqStack;
Status InitStack(SqStack &S)//初始化   
{  
    S.base=(SElemType*)malloc(sizeof(SElemType)*MAXSIZE);  
    if(!S.base)  
    exit(OVERFLOW);  
    S.top=S.base;  
    S.stacksize=MAXSIZE;  
    return OK;  
}   
//入栈 
Status Push(SqStack &S,SElemType e)
{
//插入e为新的栈顶元素
if(S.top-S.base==S.stacksize)
return ERROR;	//栈满
*S.top++=e;//将e压入栈，栈顶指针加1 
return OK; 
} 
//出栈
Status Pop(SqStack &S,SElemType &e)
{
//删除栈顶元素，用e返回其值
if(S.top==S.base)	return ERROR;//栈空
e=*--S.top; 
return OK;
} 
//取栈顶元素
SElemType GetTop(SqStack S)
{
//返回栈顶元素，不修改栈顶指针
if(S.top!=S.base)
return *(S.top-1);	
} 
Status In(SElemType c)//判断c是否是运算符 
{
	switch(c)
	{
	case '+':
	     return 1;break;
    case '-':
	     return 1;break;
    case '*':
	     return 1;break;
    case '/':
	     return 1;break;
    case '(':
    	return 1;break;
    case ')':
    	return 1;break;
    case '#':
    	return 1;break;
	default:return 0;	
	} 
}
SElemType Precede(SElemType t1,SElemType t2)//判断两个运算符的优先级关系 
{
SElemType f;
switch(t2)
{
case '+':
    if(t1=='('||t1=='#')
	f='<';
	else
	f='>';
	break;
case '-':
	if(t1=='('||t1=='#')
	f='<';
	else
	f='>';
	break;
case '*':
	if(t1=='*'||t1=='/'||t1==')')
	f='>';
	else
	f='<';
	break;
case '/':
	if(t1=='/'||t1==')')
	f='>';
	else
	f='<';
	break;
case '(':
	if(t1!=')')
	f='<';
	break;
case ')':
	if(t1=='(')
	f='=';
	else if(t1!='#')
	f='<';
	break;
case '#':
	if(t1=='#')
	f='=';
	else if(t1!='(')
	f='>';
	break;
}	
return f;
}
SElemType Operate(SElemType a,SElemType theta,SElemType b)//计算a,b操作后的数值 
{
SElemType c;
a=a-48;b=b-48;
switch(theta)
{
case '+':c=a+b+48;break;
case '-':c=a-b+48;break;
case '*':c=a*b;break;
case '/':c=a/b;break;	
} 
return c;
}

int EvaluateExpression()
{//设OPTR,OPND分别为运算符栈和操作栈
SqStack OPTR,OPND;
char ch,a,b,x,theta;
InitStack(OPTR);
InitStack(OPND);//初始化
Push(OPTR,'#');//起始符入栈
//scanf("%c",&ch);
ch=getchar();
while(ch!='#'||GetTop(OPTR)!='#')//表达式没有扫描完毕或OPTR栈顶元素不为# 
{
if(!In(ch))
{
	Push(OPND,ch); 
//scanf("%c",&ch);// 不是运算符，进OPND栈 
ch=getchar();
}
else
{switch(Precede(GetTop(OPTR),ch))//比较OPTR的栈顶元素和ch的优先级 
{
	case '<':
	     Push(OPTR,ch);
		 //scanf("%c",&ch);//压入栈，读取下一个字符 
		 ch=getchar();
	     break;
	case '>':
	    Pop(OPTR,theta); //弹出栈顶元素 运算符
	    Pop(OPND,b);Pop(OPND,a); 
	    Push(OPND,Operate(a,theta,b));
	    break;
	case '='://OPTR栈顶元素是'('且ch是')'
	    Pop(OPTR,x);//scanf("%c",&ch);
	    ch=getchar();
		break; 	
}
} }
return GetTop(OPND)-'0';	
}
int main()
{
printf("请输入算法表达式,并以#结尾：");
//EvaluateExpression();
printf("The result of expression is %dn",EvaluateExpression()); 
return 0;	
}