数据结构 实验2——表达式求值

一、实验名称：表达式求值

二、实验学时：6学时

三、实验目的

1.理解栈的结构特点和基本操作特性；

2.掌握利用栈实现表达式求值算法。

四、实验内容(步骤)

输入一个算术表达式(以“=”结束)，求其值。要求表达式以“=”结束，操作数为多位实数，对错误表达式要进行检测。

1.设置两个栈：optr算符栈和opnd操作数栈。初始置opnd为空栈；起始符“=”为optr的栈底元素；

2.自左向右扫描表达式中的每个字符c：

1)若c为操作数，则进opnd栈；

2)若c为算符，则让optr栈的栈顶元素与c比较优先级：

a.若栈顶算符优先级低于刚读入的运算符c，则让刚读入的运算符c进optr栈。

b.若栈顶算符优先级高于刚读入的运算符c，则将栈顶算符退栈，送入q；同时将操作数栈opnd退栈两次，得到两个操作数b、a，对a、b进行aqb运算后，将运算结果作为中间结果推入opnd栈。

c.若栈顶运算符的优先级与刚读入的运算符c相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。

3.直到扫描到c为定界符，即optr栈的栈顶元素和当前读入的字符均为“=”，则整个表达式求值完毕。

实验源代码

#include
#include
#include

#define MAXSIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

using namespace std;

typedef int DataType;

typedef struct
{
	DataType data[MAXSIZE];
	int top;	
}SqStack;

int InitStack(SqStack &S) // 构造一个空栈 S 
{
	S.top=-1;
	return OK;
}

int StackEmpty(SqStack S) // 判栈为空栈时返回值为真，反之为假 
{
	return(S.top==-1?TRUE:FALSE); 
}

int StackFull(SqStack S) // 判栈为满栈时返回值为真，反之为假 
{
	return(S.top==MAXSIZE-1?TRUE:FALSE); 
}

int Push(SqStack &S,DataType e) // 将元素e插入到栈中，作为新栈顶 
{
	if(StackFull(S))
	return ERROR; // 栈满
	S.top++; // top+1，栈顶位置上移
	S.data[S.top]=e;
	return OK; 
}

int Pop(SqStack &S,DataType &e) // 若栈不为空，则删除栈顶元素 
{
	if(StackEmpty(S))
	return ERROR; // 栈空
	e=S.data[S.top];
	S.top--;
	return OK; 
}

DataType GetTop(SqStack S) // 若栈不为空，则取栈顶元素 
{
	DataType e;
	if(StackEmpty(S))
	return ERROR; // 栈空
	e=S.data[S.top]; // 取出数据，top不变
	return e; 
}

char Precede(char a,char b) // 比较两个算符的优先级 
{
	char z;
	if((b=='+')||(b=='-')||(b=='*')||(b=='/')||(b=='(')||(b==')')||(b=='='))
	switch(a)
	{
		case '+':
		case '-':
			if((b=='*')||(b=='/')||(b=='('))
			    z='<';
			else
			    z='>';break;
		case '*':
		case '/':
			if(b=='(')
			    z='<';
			else
			    z='>';break;
		case '(':
			if (b=='=')
			    z='E';
		    else if(b==')')
		        z='=';
		    else z='<';
		    break;
		case ')':
			if(b=='(')
			    z='E';
			else
				z='>';
			break;
		case '=':
			if(b=='=')
			    z='=';
			else if(b==')')
			    z='E';
			else z='<';break;
	}
	else z='E';
	return(z);
}

int In(char ch) // 判断字符ch是否为算符
{
	int i,flag=0;
	char op[7]={'+','-','*','/','(',')','='};
	for(i=0;i<7;i++)
	{
		if(ch==op[i])
		{
			flag=1;break;
		}
    }
    return flag;
}

DataType Operate(DataType a,char theta,DataType b)
{
	DataType z;
	switch(theta)
	{
		case '+':z=a+b;break;
		case '-':z=a-b;break;
		case '*':z=a*b;break;
		case '/':z=a/b;break;	
	}
	return(z);
}

int CaculateExpression()
{
	SqStack optr,opnd;
	DataType x,theta,a,b,s;
	char c;
	c=getchar();
	InitStack(optr);
	Push(optr,(DataType)'=');
	InitStack(opnd);
	
	while(c!='=' || (char)GetTop(optr)!='=')
	{
		if(!In(c))
		{
			s=c-48; // s=c-'0'; 
			Push(opnd,(DataType)s);
			c=getchar();
		}
		else
		switch(Precede((char)GetTop(optr),c))
		{
			case '<': // 栈顶算符优先级低
				Push(optr,(DataType)c);
				c=getchar();
				break;
			case '=': // 优先级相同，脱去括号
				Pop(optr,x);
				c=getchar();
				break;
			case '>': // 栈顶算符优先级高，退栈并将运算
				Pop(optr,theta);
				Pop(opnd,b);
				Pop(opnd,a);
				Push(opnd,Operate(a,(char)theta,b));
			    break;
			case 'E':printf("表达式中括号不匹配！");exit(1);
		}
	}
	return GetTop(opnd);
}

int main()
{
	printf("%d\n",CaculateExpression());
	return 0;	
}

运行结果