【数据结构】中缀表达式转后缀表达式（带括号）用栈实现

中缀表达式：9+(3-1)*3+10/2

转化为后缀表达式：931-3*+102/+

规则：

从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或是优先级不高于栈顶符号则栈顶元素依次出栈并输出，并将当前符号进栈，直到最终输出后缀表达式为止。

代码是用最简单的逻辑写的，没有绕任何弯子，绝对可以看懂。我是新手，勿喷望指正。

代码 c++：VS2013 + WIN7

#include <iostream>
using namespace std;

#define ok 0
#define error -1

typedef int Elemtype;
typedef int status;//函数返回的状态，如ok  error

typedef struct StackNode
{
	Elemtype data;
	struct StackNode *next;
}StackNode, *StackNodeP;

typedef struct LinkStack
{
	StackNodeP top;
	int count;
}LinkStack;

LinkStack* LinkStack_Create();//链栈的创建
status LinkStack_Clear(LinkStack* stack);//链栈的清空
int LinkStack_Isempty(LinkStack* stack);//链栈是否为空
status LinkStack_Push(LinkStack* stack, Elemtype e);//链栈的入栈
Elemtype LinkStack_Pop(LinkStack* stack);//链栈的出栈
int LinkStack_Length(LinkStack* stack);//链栈的长度
Elemtype LinkStack_Top(LinkStack* stack);//链栈的头部元素

status change(char* buf,char* afterbuf)
{
	int i=0;
	LinkStack* LS = LinkStack_Create();
	/*
	设定+   1
		-   2
		*   3
		/   4 
	*/
	while (*buf)
	{
		if ((*buf >= '0') && (*buf <= '9'))
		{
			while ((*buf >= '0') && (*buf <= '9'))
			{
				afterbuf[i] = *buf;
				buf++;
				i++;
			}
			afterbuf[i++] = ',';		
		}
		if (*buf == '+')
		{
			if (LinkStack_Isempty(LS))//如果链栈为空，则直接将‘+’入栈
				LinkStack_Push(LS, 1);	
			else if ( LinkStack_Top(LS)> 2)//如果链栈的头结点上为‘*’‘/’，则栈中所有都弹出
			{
				while (!LinkStack_Isempty(LS))//直到将栈中的所有都弹出
				{
					if (LinkStack_Top(LS) == -1)//如果为'（'则停止循环
					{
						break;
					}
					else
					{
						switch (LinkStack_Top(LS))
						{
						case 1:
							afterbuf[i++] = '+'; afterbuf[i++] = ','; break;
						case 2:
							afterbuf[i++] = '-'; afterbuf[i++] = ','; break;
						case 3:
							afterbuf[i++] = '*'; afterbuf[i++] = ','; break;
						case 4:
							afterbuf[i++] = '/'; afterbuf[i++] = ','; break;
						}
					}					
					LinkStack_Pop(LS);
				}
				LinkStack_Push(LS, 1);
			}
			else//如果链栈中也是‘+’‘-’则直接入栈
				LinkStack_Push(LS, 1);
			buf++;
		}
		if (*buf == '-')
		{
			if (LinkStack_Isempty(LS))//如果链栈为空，则直接将‘+’入栈
				LinkStack_Push(LS, 2);
			else if (LinkStack_Top(LS)> 2)//如果链栈的头结点上为‘*’‘/’，则栈中所有都弹出
			{
				while (!LinkStack_Isempty(LS))//直到将栈中的所有都弹出
				{
					if (LinkStack_Top(LS) == -1)//如果为'（'则停止循环
					{
						break;
					}
					else
					{
						switch (LinkStack_Top(LS))
						{
						case 1:
							afterbuf[i++] = '+'; afterbuf[i++] = ','; break;
						case 2:
							afterbuf[i++] = '-'; afterbuf[i++] = ','; break;
						case 3:
							afterbuf[i++] = '*'; afterbuf[i++] = ','; break;
						case 4:
							afterbuf[i++] = '/'; afterbuf[i++] = ','; break;
						}
					}
					LinkStack_Pop(LS);
				}
				LinkStack_Push(LS, 2);
			}
			else//如果链栈中也是‘+’‘-’则直接入栈
				LinkStack_Push(LS, 2);
			buf++;
		}
		if (*buf == '*')//如果为'*'直接入栈
		{
			LinkStack_Push(LS, 3);
			buf++;
		}
		if (*buf == '/')//如果为'/'直接入栈
		{
			LinkStack_Push(LS, 4);
			buf++;
		}
		if (*buf == '(')//如果为左括号则直接进栈
		{
			LinkStack_Push(LS, -1);
			buf++;
		}
		if (*buf == ')')//如果为右括号则出栈直到左括号
		{
			while (LinkStack_Top(LS) != -1)
			{
				switch (LinkStack_Top(LS))
				{
				case 1:
					afterbuf[i++] = '+'; afterbuf[i++] = ','; break;
				case 2:
					afterbuf[i++] = '-'; afterbuf[i++] = ','; break;
				case 3:
					afterbuf[i++] = '*'; afterbuf[i++] = ','; break;
				case 4:
					afterbuf[i++] = '/'; afterbuf[i++] = ','; break;
				}
				LinkStack_Pop(LS);
			}
			LinkStack_Pop(LS);//最后把左括号给弹出来
			buf++;
		}
	}
	while (!LinkStack_Isempty(LS))
	{
		switch (LinkStack_Top(LS))
		{
		case 1:
			afterbuf[i++] = '+'; afterbuf[i++] = ','; break;
		case 2:
			afterbuf[i++] = '-'; afterbuf[i++] = ','; break;
		case 3:
			afterbuf[i++] = '*'; afterbuf[i++] = ','; break;
		case 4:
			afterbuf[i++] = '/'; afterbuf[i++] = ','; break;
		}
		LinkStack_Pop(LS);
	}
	return NULL;
}

int main(void)
{
	char* buf = (char*)malloc(sizeof(char));
	char afterbuf[1024] = {0};
	cin >> buf;
	change(buf,afterbuf);//中缀表达式转后缀表达式
	cout << afterbuf<<endl;
	system("pause");
}

//链栈的创建
LinkStack* LinkStack_Create()
{
	LinkStack* temp = NULL;
	temp = (LinkStack*)malloc(sizeof(LinkStack));
	if (temp == NULL)
		cout << "LinkStack_create 出错"<< endl;
	temp->count = 0;
	temp->top= NULL;
	return temp;
}
//链栈的清空
status LinkStack_Clear(LinkStack* stack)
{
	if (stack == NULL)
		return ok;
	stack->top->next = NULL;
	stack->count = 0;
	return ok;
}
//链栈是否为空
int LinkStack_Isempty(LinkStack* stack)
{
	if (stack == NULL)
		return error;
	return stack->top == NULL ? 1 : 0;
}

//链栈的长度
int LinkStack_Length(LinkStack* stack)
{
	if (stack == NULL)
		return error;
	return stack->count;
}
//链栈的入栈
status LinkStack_Push(LinkStack* stack, Elemtype e)
{
	if (stack == NULL)
		return error;
	LinkStack* temp = NULL;
	temp = (LinkStack*)stack;

	StackNodeP SNP = (StackNodeP)malloc(sizeof(StackNode));
	SNP->data = e;
	SNP->next = temp->top;
	temp->top = SNP;

	temp->count++;
	return ok;
}
//链栈的出栈
Elemtype LinkStack_Pop(LinkStack* stack)
{
	if (stack == NULL)
		return error;
	LinkStack* temp = NULL;
	temp = (LinkStack*)stack;
	Elemtype node = temp->top->data;//这是将要删除的元素缓存下来
	StackNodeP p = temp->top;//将栈顶结点赋值给p
	temp->top = temp->top->next;//栈顶指针下移一位，指向后一个结点
	free(p);//释放结点

	temp->count--;
	return node;
}
//链栈的头部元素
Elemtype LinkStack_Top(LinkStack* stack)
{
	if (stack == NULL)
		return error;

	return stack->top->data;
}

侧视图：