中缀表达式转后缀表达式（栈）

大家好，欢迎来到IT知识分享网。

这里给出中缀表达式转后缀表达式的算法过程，以及再举两个例子

算法过程：

1. 数字直接加入后缀表达式
2.如果是‘(’, 入栈
3.如果是‘)’, 则依次把栈中的运算符加入后缀表达式，直到出现‘(’并从栈中删除它
4. 如果是运算符 + – * /
    a.栈空或者栈顶元素为‘(’, 入栈
    b.高于栈顶元素优先级，入栈
    c.否则依次弹出栈顶运算符，直到遇到一个优先级小于它的运算符或者是遇到‘(’为止
5.遍历完成后，如果栈非空则依次弹出所有栈顶元素加入到表达式当中

例1：

例2：

code:

#include <stdio.h> 
#include <string.h> 

#define MaxSize 100 

typedef struct{
	char data[MaxSize];
	int top; // 栈顶指针 指向栈顶元素 
} SeqStack;

// 顺序栈初始化 
void StackInit(SeqStack s)
{
	s.top = 0;
	memset(s.data, 0, sizeof(s.data));
}
// 入栈 
bool StackPush(SeqStack &s, char e)
{
	if(s.top == MaxSize){
		return false;
	}
	s.data[s.top++] = e;
	return true;
}
// 出栈 
bool StackPop(SeqStack &s)
{
	if(s.top == 0){
		return false;
	}
	s.data[s.top-1] = '\0';
	s.top--;
	return false;
}
// 获取栈顶元素 
char GetTop(SeqStack s)
{
	return s.data[s.top-1];
}
// 判断栈是否为空 
bool StackIsEmpty(SeqStack s)
{
	return (s.top == 0 ? true : false);
}
// 优先级比较 
bool check(char ch1, char ch2) // 只有ch1的优先级小于ch2的优先级时返回true 
{
	if((ch1 == '+' || ch1 == '-') && (ch2 == '*' || ch2 == '/')){
		return true;
	}
	return false;
}
// 三个参数分别时 栈，目标表达式，转换后的结果 
void solve(SeqStack &s, char *str, char *ans)
{
	int idx = 0; // ans的下标 
	int len = strlen(str);
	for(int i = 0; i < len; i++){
		if(str[i] >= '0' && str[i] <= '9'){ // 数字加入表达式 
			ans[idx] = str[i];
			idx++;
		}
		else if(str[i] == '(' || StackIsEmpty(s) || GetTop(s) == '('){ // 栈为空或栈顶为左括号 入栈 
			StackPush(s, str[i]);
		}
		else if(str[i] == ')'){ // 如果为右括号 
			do{
				ans[idx] = GetTop(s);
				idx++; 
				StackPop(s);
			}while(GetTop(s) != '(' );
			StackPop(s); // 删除左括号 
		}
		// 当前元素是运算符 如果优先级高于栈顶元素 入栈 
		else if(check(GetTop(s),str[i])){
			StackPush(s, str[i]);
		}
		else{ // 其他情况->当前元素是运算符且不能入栈 
			do{
				ans[idx] = GetTop(s);
				idx++;
				StackPop(s);
			}while(!(check(GetTop(s), str[i]) || GetTop(s) == '(') ); 
			StackPush(s, str[i]);
		}
	}
	while(!StackIsEmpty(s)){ // 栈内有剩余运算符则加入表达式 
		ans[idx++] = GetTop(s);
		StackPop(s);
	}
	ans[idx] = '\0'; // 确保ans为字符串不会有多余内容 
}

int main()
{
	SeqStack s;
	StackInit(s);
	char str[MaxSize], ans[MaxSize] = {0};
	scanf("%s", str);
	solve(s, str, ans);
	printf("%s\n", ans);
	
	return 0;
}