数据结构实战

        本节我们来利用栈的特性来进行表达式的求值。假定我们输入的表达式是正确的，程序将按下面的过程进行求值：

        准备两个栈stack_oper用于存放操作符，stack_num用于存入操作数。

• 从头至尾遍历表达式。
• 如果当前操作内容是一个数字，则入操作数栈。
• 如果当前操作内容是一个操作符，并且操作符栈顶元素为空，则入操作符栈。
• 如果操作符栈顶元素不为空，则用操作符栈顶元素与当前操作符比较优先级。
• 如果操作符栈顶元素优先级比与当前操作符优先级低，则对当前操作符入栈。
• 如果操作符栈顶优先级与当前操作符优先级相同，去括号。
• 如果操作符栈顶优先级与当前操作符优先级高，则按操作符栈顶元素计算操作数栈顶两个元素的结果，并再次存入操作数栈。
• 直到表达式结束。

         下面来看一下操作符的优先级：

        这里为了程序实现方便，额外加入一个#操作符用于表示表达式结束，它的优先级小于其它操作符。

        下面我们来编写这个表达式求值的程序：

//定义操作符
char opers[7] =
{ '+', '-', '*', '/', '(', ')', '#' };

// 定义操作符的运算优先级
char oper_rule[7][7] =
{
// +
        '>', '>', '<', '<', '<', '>', '>',
        // -
        '>', '>', '<', '<', '<', '>', '>',
        // *
        '>', '>', '>', '>', '<', '>', '>',
        // /
        '>', '>', '>', '>', '<', '>', '>',
        // (
        '<', '<', '<', '<', '<', '=', ' ',
        // )
        '>', '>', '>', '>', ' ', '>', '>',
        // #
        '<', '<', '<', '<', '<', ' ', '=' };

//计算操作符优先级
char get_oper_rule(char operL, char operR)
{
	int i = 0;
	int j = 0;
	//取得左侧操作符下标
	for (; i < 7; i++)
	{
		if (opers[i] == operL)
		{
			break;
		}
	}
	//取得右侧操作符下标
	for (; j < 7; j++)
	{
		if (opers[j] == operR)
		{
			break;
		}
	}
	//返回优先级
	return oper_rule[i][j];
}

//根据操作符和操作数做计算
int operate(int a, int b, char oper)
{
	int result = 0;
	switch (oper)
	{
		case '+':
			result = a + b;
			break;

		case '-':
			result = a - b;
			break;

		case '*':
			result = a * b;
			break;

		case '/':
			result = a / b;
			break;
	}
	return result;
}

void free_char(char *ch)
{
	free(ch);
}

void free_int(int *i)
{
	free(i);
}

int main(int argc, char **args)
{
	char *str = (char *) malloc(200);
	do
	{
		printf("Please enter the expression(Enter \"exit\" to quit): ");
		scanf("%s", str);

		if (strcmp(str, "exit") == 0)
		{
			break;
		}

		int len = strlen(str);
		str[len] = '#';
		str[len + 1] = '\0';
		//构建栈
		s_stack stack_oper;
		s_stack stack_num;

		stack_init(&stack_oper, free_char);
		stack_init(&stack_num, free_int);

		char *ch_i = (char *) malloc(1);
		*ch_i = '#';
		stack_push(&stack_oper, ch_i);

		char *p = str;
		while (*p != '\0')
		{
			//如果是操作符则入操作符栈或计算
			if (*p == '#' || *p == '+' || *p == '-' || *p == '*' || *p == '/' || *p == '(' || *p == ')')
			{
				//栈顶元素出栈做比较
				char *ch;
				stack_pop(&stack_oper, &ch);

				//与当然操作符做优先级比较
				char oper_rule_re = get_oper_rule(*ch, *p);
				//优先级低，入操作符栈
				if (oper_rule_re == '<')
				{
					stack_push(&stack_oper, ch);
					ch = (char *) malloc(1);
					*ch = *p;
					stack_push(&stack_oper, ch);
					p++;
				}
				//优先级相同，去括号
				else if (oper_rule_re == '=')
				{
					//如果是#则结束
					if (*ch == '#')
					{
						free_char(ch);
						break;
					}
					free_char(ch);
					p++;
				}
				//优先级高，计算操作数并将结果入栈
				else if (oper_rule_re == '>')
				{
					int *numA;
					int *numB;
					int *numR = (int *) malloc(sizeof(int));
					stack_pop(&stack_num, &numA);
					stack_pop(&stack_num, &numB);
					*numR = operate(*numB, *numA, *ch);
					stack_push(&stack_num, numR);

					free_char(ch);
					free_int(numA);
					free_int(numB);
				}
			}
			//如果是数字则入数字栈
			else
			{
				//将字符串中的数据转为int型
				int i = 0;
				int *num = (int *) malloc(sizeof(int));
				for (; p[i] >= 48 && p[i] <= 57; i++)
				{
					if (i == 0)
					{
						*num = (int) p[i] - 48;
					}
					else
					{
						*num *= 10;
						*num += (int) p[i] - 48;
					}
				}
				//数字入栈
				stack_push(&stack_num, num);
				p += i;
			}
		}

		//显示最终运算结果
		int *numR;
		stack_pop(&stack_num, &numR);
		printf("Result is %d.\n", *numR);

		//销毁栈
		stack_destroy(&stack_oper);
		stack_destroy(&stack_num);

	}
	while (1);

	free(str);

	return 0;
}

        运行结果：

Please enter the expression(Enter "exit" to quit): (1+2)*3-4
Result is 5.
Please enter the expression(Enter "exit" to quit): (1+2)*3-4*(5+4/2)
Result is -19.
Please enter the expression(Enter "exit" to quit): 3*4+15*(1+3)/2
Result is 42.
Please enter the expression(Enter "exit" to quit): exit

        本例代码：

code path   chapter.02/e.g.2.3/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure