数据结构实验三 栈的应用——算术表达式求值

一、实验目的

1. 掌握栈和队列的两种存储结构；
2. 掌握栈和队列的实现；
3. 掌握栈和队列的应用。

二、实验相关知识

1. 复习C语言文件读写的相关知识
2. 复习课本中第3章关于栈和队列的相关知识点；

三、实验内容与要求

1.编程实现对算术表达式的求值。

【设计要求】输入包含+-*/四种运算，以及包含()括号的合法算术表达式，并计算其值，表达式以#开始，并以#结束。

【测试用例】

#(3)#   
#3+4#
#3+4*2#
#(3+4)*2#
#(2*(3+4)-2)+(3-1)#
#(11+12)*16#

【栈应用分析】以测试用例：#16 * (11+12) #  为例，分析栈操作的过程，详细见“算术表达式计算的栈操作过程.ppt”文件。

四、程序代码及运行结果

【程序代码】

#include <iostream>
using namespace std;

#define TRUE 1
#define FALSE 0
#define Stack_Size 50

/*int栈*/
typedef struct
{
	int elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
	int top;          		/*用来存放栈顶元素的下标，top为-1表示空栈*/
}IntStack;

/*char栈*/
typedef struct
{
	char elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
	int top;          		/*用来存放栈顶元素的下标，top为-1表示空栈*/
}CharStack;

/*初始化int栈*/
void InitStack(IntStack *&S)
{
	S = (IntStack *)malloc(sizeof(IntStack));
	S->top = -1;
}
/*初始化char栈*/
void InitStack(CharStack *&S)
{
	S = (CharStack *)malloc(sizeof(CharStack));
	S->top = -1;
}
/*判栈空*/
int IsEmpty(IntStack *S) /*判断栈S为空栈时返回值为真，反之为假*/
{
	return(S->top == -1 ? TRUE : FALSE);
}
/*判栈空*/
int IsEmpty(CharStack *S) /*判断栈S为空栈时返回值为真，反之为假*/
{
	return(S->top == -1 ? TRUE : FALSE);
}

/*判栈满*/
int IsFull(IntStack *S)	/*判断栈S为满栈时返回值为真，反之为假*/
{
	return(S->top == Stack_Size - 1 ? TRUE : FALSE);
}
/*判栈满*/
int IsFull(CharStack *S)	/*判断栈S为满栈时返回值为真，反之为假*/
{
	return(S->top == Stack_Size - 1 ? TRUE : FALSE);
}
/*进栈*/
int Push(CharStack *&S, char x)
{
	if (S->top == Stack_Size - 1)
		return(FALSE);  /*栈已满*/
	S->top++;
	S->elem[S->top] = x;
	return(TRUE);
}
/*进栈*/
int Push(IntStack *&S, int x)
{
	if (S->top == Stack_Size - 1)
		return(FALSE);  /*栈已满*/
	S->top++;
	S->elem[S->top] = x;
	return(TRUE);
}
/*出栈*/
int Pop(IntStack *&S, int &x)
{
	/* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
	if (S->top == -1)  /*栈为空*/
		return(FALSE);
	else
	{
		x = S->elem[S->top];
		S->top--;    /* 修改栈顶指针 */
		return(TRUE);
	}
}
/*出栈*/
int Pop(CharStack *S, char &x)
{
	/* 将栈S的栈顶元素弹出，放到x所指的存储空间中 */
	if (S->top == -1)  /*栈为空*/
		return(FALSE);
	else
	{
		x = S->elem[S->top];
		S->top--;    /* 修改栈顶指针 */
		return(TRUE);
	}
}

/*取栈顶元素。*/
int GetTop(IntStack *S, int &x)
{
	/* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */
	if (S->top == -1)  /*栈为空*/
		return(FALSE);
	else
	{
		x = S->elem[S->top];
		return(TRUE);
	}
}
/*取栈顶元素。*/
int GetTop(CharStack *S, char &x)
{
	/* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */
	if (S->top == -1)  /*栈为空*/
		return(FALSE);
	else
	{
		x = S->elem[S->top];
		return(TRUE);
	}
}

void trans(char *exp, char postexp[])
{
	char e;
	CharStack *Optr;
	InitStack(Optr);
	int i = 0;
	while (*exp != '\0')
	{
		switch (*exp)
		{
		case'(':
			Push(Optr, '(');
			exp++;
			break;
		case')':
			Pop(Optr, e);
			while (e != '(')
			{
				postexp[i++] = e;
				Pop(Optr, e);
			}
			exp++;
			break;
		case'+':
		case'-':
			while (!IsEmpty(Optr))
			{
				GetTop(Optr, e);
				if (e != '(')
				{
					postexp[i++] = e;
					Pop(Optr, e);
				}
				else break;
			}
			Push(Optr, *exp);
			exp++;
			break;
		case'*':
		case'/':
			while (!IsEmpty(Optr))
			{
				GetTop(Optr, e);
				if (e == '*' || e == '/')
				{
					postexp[i++] = e;
					Pop(Optr, e);
				}
				else break;
			}
			Push(Optr, *exp);
			exp++;
			break;
		default:
			while (*exp >= '0'&&*exp <= '9')
			{
				postexp[i++] = *exp;
				exp++;
			}
			postexp[i++] = '#';
		}
	}
	while (!IsEmpty(Optr))
	{
		Pop(Optr, e);
		postexp[i++] = e;
	}
	postexp[i] = '\0';
	/*DestroyStack(Optr);*/
}
double compvalue(char *postexp)
{
	int d = 0, a = 0, b = 0, c = 0, e = 0;
	IntStack *Opnd;//定义操作数栈
	InitStack(Opnd);			//初始化操作数栈
	while (*postexp != '\0')		//postexp字符串未扫描完时循环
	{
		switch (*postexp)
		{
		case '+':			//判定为'+'号
			Pop(Opnd, a);		//出栈元素a
			Pop(Opnd, b);		//出栈元素b
			c = b + a;			//计算c
			Push(Opnd, c);		//将计算结果c进栈
			break;
		case '-':				//判定为'-'号
			Pop(Opnd, a);		//出栈元素a
			Pop(Opnd, b);		//出栈元素b
			c = b - a;			//计算c
			Push(Opnd, c);		//将计算结果c进栈
			break;
		case '*':				//判定为'*'号
			Pop(Opnd, a);		//出栈元素a
			Pop(Opnd, b);		//出栈元素b
			c = b*a;			//计算c
			Push(Opnd, c);		//将计算结果c进栈
			break;
		case '/':				//判定为'/'号
			Pop(Opnd, a);		//出栈元素a
			Pop(Opnd, b);		//出栈元素b
			if (a != 0)
			{
				c = b / a;			//计算c
				Push(Opnd, c);		//将计算结果c进栈
				break;
			}
			else
			{
				printf("\n\t除零错误!\n");
				exit(0);			//异常退出
			}
			break;
		default:			//处理数字字符
			d = 0;		//转换成对应的数值存放到d中
			while (*postexp >= '0' && *postexp <= '9')
			{
				d = 10 * d + *postexp - '0';
				postexp++;
			}
			Push(Opnd, d);	//将数值d进栈
			break;
		}
		postexp++;		//继续处理其他字符
	}
	GetTop(Opnd, e);		//取栈顶元素e
	return e;			//返回e
}

int main(int heng, char * heng1[])
{
	char exp[Stack_Size];
	int i = 0;
	gets_s(exp);
	char postexp[Stack_Size];
	trans(exp, postexp);
	printf("中缀表达式:%s\n", exp);
	printf("后缀表达式:%s\n", postexp);
	printf("表达式的值:%g\n", compvalue(postexp));
	return 0;
}

【运行结果】

【算法描述】

（1）将算术表达式转换成后缀表达式
exp => postexp
扫描exp的所有字符：
数字字符直接放在postexp中
运算符通过一个栈来处理优先级
情况1（没有括号）
先进栈的先退栈即先执行：
只有大于栈顶优先级才能直接进栈
exp扫描完毕，所有运算符退栈
情况2（带有括号）
开始时，任何运算符都进栈
(：一个子表达式开始，进栈
栈顶为(：任何运算符进栈
)：退栈到（
只有大于栈顶的优先级，才进栈；否则退栈
（2）后缀表达式求值
postexp => 值
扫描postexp的所有字符：
数字字符：转换为数值并进栈
运算符：退栈两个操作数，计算，将结果进栈

五、实验心得体会

通过这次试验，我对栈有了新的理解和认识。