数据结构07：栈的应用（表达式求值）

摘要：表达式求值是对栈的一个进阶应用，巧妙地运用了栈的特性，创建了两个栈，一个存放数值，一个存放运算符。看懂这个代码，我们就会对栈的理解更进一步。

实际是这个代码是不好写的，我参考了教材相关内容及其他同学的代码后，才理解并写出以下代码。

由于栈的基本操作等已经在前文说过，这里先只展示有关表达式求值的函数
一.代码块
1）判断优先级函数

char priority(char ch1,char ch2)
{
	//对于优先级的判定，我在书上找到了一个表。对此用二位数组实现比较方便
	
	//书上是添加一个#号代表表达式结束，这里可以用=号方便理解 
	int i,j;
	char pri[7][7] = 
	{//   +   -   *   /   (   )   =
		{'>','>','<','<','<','>','>'},
		{'>','>','<','<','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'<','<','<','<','<','=',''},
		{'>','>','>','>','','>','>'},
		{'<','<','<','<','<','','='},
	};
	
	switch (ch1)
	{
		case '+':
			i = 0;
			break;
		case '-':
			i = 1;
			break;
		case '*':
			i = 2;
			break;	
		case '/':
			i = 3;
			break;	
		case '(':
			i = 4;
			break;
		case ')':
			i = 5;
			break;
		case '=':
			i = 6;
			break;			
	}
	
	switch (ch2)
	{
		case '+':
			j = 0;
			break;
		case '-':
			j = 1;
			break;
		case '*':
			j = 2;
			break;	
		case '/':
			j = 3;
			break;	
		case '(':
			j = 4;
			break;
		case ')':
			j = 5;
			break;
		case '=':
			j = 6;
			break;			
	}
	
	return pri[i][j];
}

2）判断字符是否为数字

int isDigit(char ch)
{
	if(ch >= '0' && ch <= '9')
	{
		return 1;
	}
	return 0;
}

3）判断是否为运算符

int isOperator(char ch)
{
	switch (ch)
	{
		case '+':
		case '-':
		case '*':
		case '/':
		case '(':
		case ')':
		case '=':
			return 1;
		
		default :
			return 0;
	}
}

4）运算函数

int evaluate(int x,char ch ,int y)
{
	switch (ch)
	{
		case '+':
			return x+y;
		case '-':
			return x-y;
		case '*':
			return x*y;
		case '/':
			if(y == 0)
			{
				printf("除数为0，无效的表达式n"); 
				return -1;
			}
			else
			{
				return x/y;
			}
	}
}

5）关键函数：处理表达式

int evaluateExpression(char *paraExpression)
{
	charStackPtr stack1 = stackInit();//存放数的栈 
	charStackPtr stack2 = stackInit();//存放运算符的栈 
	
	int i,a,b,x,x1,x2;
	char tempch1,tempch2;
	
	push(stack2,'=');//我们手动添加等号 
	i = 0;
	tempch1 = paraExpression[i++];
	while(tempch1 != '=' || getTop(stack2) != '=')
	{
		if(isOperator(tempch1))//判断是否为运算符 
		{
			switch(priority(getTop(stack2),tempch1))
			{
				case'<':
					push(stack2,tempch1);
					tempch1 = paraExpression[i++];
					break;
				case'>':
					tempch2 = pop(stack2);
					b = pop(stack1);
					a = pop(stack1);
					push(stack1,evaluate(a,tempch2,b));
					break;
				case'=':
					x = pop(stack2);
					tempch1 = paraExpression[i++];
					break;
			}
		 }
		 else if(isdigit(tempch1))
		 {
		 	x1 = tempch1-'0';
		 	push(stack1,x1);
		 	x2 = x1;
		 	tempch1 = paraExpression[i++];
		 	
		 	while(isDigit(tempch1))
		 	{
		 		x1 = tempch1 - '0';
		 		x2 = 10*x2 + x1;
		 		x = pop(stack1);
		 		push(stack1,x2);
		 		tempch1 = paraExpression[i++];
			 }
		 } 
		else if(tempch1 == ' ')
		{
			while(tempch1 == ' ')
			{
				tempch1 == paraExpression[i++];
			}
		}
		else
		{
			printf("多项式错误n");
		}
	 }
	return getTop(stack1);
}

6）测试函数

void evaluateExpressionText()
{
	printf("Text begin---------n");
	int result;
	char *tempExpression="5*3-(8/2+4)+8*9-24=";
	result = evaluateExpression(tempExpression);
	printf("%s%dn",tempExpression,result);
	
	tempExpression="210-29+(59*2-33+12)-101=";
	result = evaluateExpression(tempExpression);
	printf("%s%dn",tempExpression,result);
	
	tempExpression="7*(4+2)-(3*21)=";
	result = evaluateExpression(tempExpression);
	printf("%s%dn",tempExpression,result);
	printf("Text over----------n");
}

三.全部代码

#include 
#include 

#define MAXSIZE 10

typedef struct charStack
{
	int top; 
	int data[MAXSIZE];
}*charStackPtr;

charStackPtr stackInit()
{
	charStackPtr resultStack = (charStackPtr)malloc(sizeof(struct charStack));
	
	resultStack->top = -1;
	return resultStack;
}

void outputStack(charStackPtr paraStack)
{
	int i;
	for(i = 0;i <= paraStack->top;i ++)
	{
		printf("%c ",paraStack->data[i]); 
	}
	
	printf("rn");
}

void push(charStackPtr paraStack,char paraChar)
{
	if(paraStack->top >= MAXSIZE-1)
	{
		printf("Cannot push element:stack fullrn");
		return ;
	}
	
	paraStack->top ++;
	paraStack->data[paraStack->top] = paraChar;
}

char pop(charStackPtr paraStack)
{
	if(paraStack->top < 0)
	{
		printf("Cannot pop element:stack empty");
		return ''; 
	}
	
	paraStack->top --;
	
	return paraStack->data[(paraStack->top)+1];
}

//这个是得到栈顶元素，但不出栈 
int getTop(charStackPtr paraStackPtr)
{
	if(paraStackPtr->top < 0)
	{
		printf("空栈，不能提取rn");
		return '';
	 } 
	return paraStackPtr->data[paraStackPtr->top];
}


char priority(char ch1,char ch2)
{
	//对于优先级的判定，我在书上找到了一个表。对此用二位数组实现比较方便
	
	//书上是添加一个#号代表表达式结束，这里可以用=号方便理解 
	int i,j;
	char pri[7][7] = 
	{//   +   -   *   /   (   )   =
		{'>','>','<','<','<','>','>'},
		{'>','>','<','<','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'<','<','<','<','<','=',''},
		{'>','>','>','>','','>','>'},
		{'<','<','<','<','<','','='},
	};
	
	switch (ch1)
	{
		case '+':
			i = 0;
			break;
		case '-':
			i = 1;
			break;
		case '*':
			i = 2;
			break;	
		case '/':
			i = 3;
			break;	
		case '(':
			i = 4;
			break;
		case ')':
			i = 5;
			break;
		case '=':
			i = 6;
			break;			
	}
	
	switch (ch2)
	{
		case '+':
			j = 0;
			break;
		case '-':
			j = 1;
			break;
		case '*':
			j = 2;
			break;	
		case '/':
			j = 3;
			break;	
		case '(':
			j = 4;
			break;
		case ')':
			j = 5;
			break;
		case '=':
			j = 6;
			break;			
	}
	
	return pri[i][j];
}

int isDigit(char ch)
{
	if(ch >= '0' && ch <= '9')
	{
		return 1;
	}
	return 0;
}

int isOperator(char ch)
{
	switch (ch)
	{
		case '+':
		case '-':
		case '*':
		case '/':
		case '(':
		case ')':
		case '=':
			return 1;
		
		default :
			return 0;
	}
}

int evaluate(int x,char ch ,int y)
{
	switch (ch)
	{
		case '+':
			return x+y;
		case '-':
			return x-y;
		case '*':
			return x*y;
		case '/':
			if(y == 0)
			{
				printf("除数为0，无效的表达式n"); 
				return -1;
			}
			else
			{
				return x/y;
			}
	}
}

int evaluateExpression(char *paraExpression)
{
	charStackPtr stack1 = stackInit();//存放数的栈 
	charStackPtr stack2 = stackInit();//存放运算符的栈 
	
	int i,a,b,x,x1,x2;
	char tempch1,tempch2;
	
	push(stack2,'=');//我们手动添加等号 
	i = 0;
	tempch1 = paraExpression[i++];
	while(tempch1 != '=' || getTop(stack2) != '=')
	{
		if(isOperator(tempch1))//判断是否为运算符 
		{
			switch(priority(getTop(stack2),tempch1))
			{
				case'<':
					push(stack2,tempch1);
					tempch1 = paraExpression[i++];
					break;
				case'>':
					tempch2 = pop(stack2);
					b = pop(stack1);
					a = pop(stack1);
					push(stack1,evaluate(a,tempch2,b));
					break;
				case'=':
					x = pop(stack2);
					tempch1 = paraExpression[i++];
					break;
			}
		 }
		 else if(isdigit(tempch1))
		 {
		 	x1 = tempch1-'0';
		 	push(stack1,x1);
		 	x2 = x1;
		 	tempch1 = paraExpression[i++];
		 	while(isDigit(tempch1))
		 	{
		 		x1 = tempch1 - '0';
		 		x2 = 10*x2 + x1;
		 		x = pop(stack1);
		 		push(stack1,x2);
		 		tempch1 = paraExpression[i++];
			 }
		 } 
		else if(tempch1 == ' ')
		{
			while(tempch1 == ' ')
			{
				tempch1 == paraExpression[i++];
			}
		}
		else
		{
			printf("多项式错误n");
		}
	 }
	return getTop(stack1);
}

void evaluateExpressionText()
{
	printf("Text begin---------n");
	int result;
	char *tempExpression="5*3-(8/2+4)+8*9-24=";
	result = evaluateExpression(tempExpression);
	printf("%s%dn",tempExpression,result);
	
	tempExpression="210-29+(59*2-33+12)-101=";
	result = evaluateExpression(tempExpression);
	printf("%s%dn",tempExpression,result);
	
	tempExpression="7*(4+2)-(3*21)=";
	result = evaluateExpression(tempExpression);
	printf("%s%dn",tempExpression,result);
	printf("Text over----------n");
}


int main()
{
	evaluateExpressionText();
}

四.运行结果

Text begin---------
5*3-(8/2+4)+8*9-24=55
210-29+(59*2-33+12)-101=-79
7*(4+2)-(3*21)=-21
Text over----------