中缀表达式转后缀表达式栈的变化_利用栈实现中缀转后缀

全栈程序员站长

发布于 2022-11-15 17:34:44

4480

发布于 2022-11-15 17:34:44

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

算法过程：

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] = '#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;
}';
	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] = '#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;
}'; // 确保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;
}

Jetbrains全家桶1年46，售后保障稳定

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/226774.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年10月30日，如有侵权请联系 cloudcommunity@tencent.com 删除

https