中缀表达式转后缀表达式

理论知识

demo.cpp

#define _CRT_SECURE_NO_WARNINGS
#include "LinkStack.h"
#include<stdio.h>
#include<stdlib.h>
#include<string>
//是否是数字
int IsNumber(char c)
{
	return c >= '0' &&c <= '9';
}
//是否是左括号
int IsLeft(char c)
{
	return c =='(';
	
}
//是否是右括号
int IsRight(char c)
{
	return c ==')';
}
//操作符操作
int IsOperator(char c)
{
	return c =='+'||c=='*'||c=='-'||c=='/';
}
typedef struct MYCHAR{
	LinkNode node;
	char *p;
}Mychar;
Mychar* CreatMychar(char *p)
{
	Mychar *mychar = (Mychar*)malloc(sizeof(Mychar));
	mychar->p = p;
	return mychar;
}
//左括号操作
void Left_oprator(LinkStack *stack,char *p){
	Push_LinkStack(stack, (LinkNode*)CreatMychar(p));

}
//右括号操作
void Right_oprator(LinkStack *stack){
	//判断是否有元素
	while (Size_LinkStack(stack)>0)
	{
		Mychar *mychar = (Mychar*)Top_LinkStack(stack);
		if (IsLeft(*(mychar->p)))
		{
			Pop_LinkStack(stack);
			break;
		}
		printf("%c", *(mychar->p));
		Pop_LinkStack(stack);
		free(mychar);
	}

}
//返回运算符号优先级
int GetPriority(char c){
	if (c == '*' || c == '/')
	{
		return 2;

	}
	if (c == '+' || c == '-')
	{
		return 1;

	}
	return 0;
}
//运算符操作
void Operatoroperator(LinkStack* stack,char*p)
{
	//取栈顶元素
	
	Mychar *mychar = (Mychar*)Top_LinkStack(stack);
	if (mychar==NULL)
	{
		Push_LinkStack(stack, (LinkNode*)CreatMychar(p));
		return;
	}
	//如果栈顶元素的优先级低于当前元素 直接入栈
	if (GetPriority(*(mychar->p)) < GetPriority(*p)){
		Push_LinkStack(stack, (LinkNode*)CreatMychar(p));
		return;
	}
	//如果栈顶元素的优先级不低于当前元素
	else
	{
		
		while (Size_LinkStack(stack)>0)
		{
			Mychar *mychar = (Mychar*)Top_LinkStack(stack);
			if (GetPriority(*(mychar->p)) < GetPriority(*p)){
				Push_LinkStack(stack, (LinkNode*)CreatMychar(p));
				break;
			}
			printf("%c", *(mychar->p));
			Pop_LinkStack(stack);
			free(mychar);
		}
		
	}
	
	return;
}
int main(void)
{
	LinkStack *stack = Init_LinkStack();
	char *str = "8+(3-1)*5";
	char *p = str;
	while(*p!='\0')
	{
		//判断是否是数字
		if (IsNumber(*p))
		{
			printf("%c", *p);
		}
		//判断是否为左括号
		if (IsLeft(*p))
		{

			Left_oprator(stack, p);

		}
		//判断是否为右括号
		if (IsRight(*p))
		{
			Right_oprator(stack);
			
		}
		if (IsOperator(*p))
		{
			Operatoroperator(stack,p);
		}

		p++;
	}
	while (Size_LinkStack(stack)>0)
	{
		 Mychar*mychar=(Mychar*)Top_LinkStack(stack);
		 printf("%c", *(mychar->p));
		 Pop_LinkStack(stack);
		 free(mychar);
	}
	free(stack);
	system("pause");
	return 0;
}

栈的链式存储的cpp和h文件见资源：https://blog.csdn.net/qq_23859701/article/details/82913581
或者用栈的顺序存储：
https://blog.csdn.net/qq_23859701/article/details/82876581