栈的应用中缀转后缀表达式

发表评论

后缀表达式，由波兰科学家在20世纪50年代提出，将运算符放在数字后面，更便于计算机去计算，而我们平常看到的 1 + 2、5 * 10 等，都是中缀表达式，这种方式，符合人类的思考方式。举几个例子：

  1. 5 + 4 => 5 4 +
  2. 1 + 2 * 3 => 1 2 3 * +
  3. 8 + ( 3 – 1 ) * 5 => 8 3 1 – 5 * +

左侧为中缀表达式，右侧为后缀表达式。那这种转换的规则和方法是什么呢？首先我们来看一下规则：

【后缀表达式转换规则】

对于数字：直接输出
对于符号：
	左括号：进栈  
	运算符号：与栈顶符号进行优先级比较
	若栈顶符号优先级低：此符号进栈  
	（默认栈顶若是左括号，左括号优先级最低）
	若栈顶符号优先级不低：将栈顶符号弹出并输出，之后进栈
	右括号：将栈顶符号弹出并输出，直到匹配左括号

【使用栈模型实现以上功能】

注意，以下代码需要用到栈模型链式储存的实现头文件 LinkStack.h 和 LinkStack.c：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkStack.h"

// 判断是不是数字
int is_num(char ch)
{
	return ch >= '0' && ch <= '9';
}

// 判断是不是左括号
int is_left(char ch)
{
	return ch == '(';
}

// 判断是不是右括号
int is_right(char ch)
{
	return ch == ')';
}

// 判断是不是操作符
int is_operator(char ch)
{
	return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

// 判断优先级
int priority(char ch)
{
	int result = 0;

	if (ch == '+' || ch == '-')
		result = 1;
	else if (ch == '*' || ch == '/')
		result = 2;

	return result;
}

void output(char c)
{
	//字符不为0便输出
	if (c != '\0')
	{
		printf("%c", c);
	}
}

void process(char* code)
{
	LinkStack* stack = LinkStack_Create();
	int i = 0;
	while (code[i] != '\0')
	{
		// 如果是数字直接输出
		if (is_num(code[i]))
		{
			output(code[i]);
		}
		// 判断是不是操作符
		if (is_operator(code[i]))
		{
			// 若栈顶符号优先级低：此符号进栈  
			//（默认栈顶若是左括号，左括号优先级最低）
			// 若栈顶符号优先级不低：将栈顶符号弹出并输出
			while (priority(code[i]) <= priority((char)(int)LinkStack_Top(stack)))
			{
				// 弹出并输出
				output((char)(int)LinkStack_Pop(stack));
			}
			// 之后压栈
			LinkStack_Push(stack, (void*)(int)code[i]);
		}
		// 判断是不是左括号
		if (is_left(code[i]))
		{
			LinkStack_Push(stack, (void*)(int)code[i]);
		}
		// 判断是不是右括号，如果是与栈内左括号匹配
		if (is_right(code[i]))
		{
			// 循环判断是不是左括号，不是则弹出栈顶元素，循环弹出直至遇到左括号为止
			while (!is_left((char)(int)LinkStack_Top(stack)))
			{
				// 弹出并输出栈顶内容
				output((char)(int)LinkStack_Pop(stack));
			}
			// 此时弹出的一定是左括号
			LinkStack_Pop(stack);
		}
		// 下标++
		i++;
	}

	while (LinkStack_Size(stack))
	{
		// 输出栈中内容
		output((char)(int)LinkStack_Pop(stack));
	}

	// 销毁栈
	LinkStack_Destroy(stack);
}

int main(int argc, char* argv[])
{
	char* code = "8+(3-1)*5";
	process(code);
	return 0;
}

 

发表评论