中缀表达式转后缀表达式

求解思路请看这位大佬的博客，讲的很详细

https://blog.csdn.net/ssjhust123/article/details/8001651

下面贴上我自己实现的代码

#include<iostream>
#include<cstdlib>
using namespace std;

#define INITSIZE 20  // 定义栈初始大小 
#define INCREMENTSIZE 10  // 扩容时每次增加的容量 
#define OVERFLOW -1    // 错误状态码 
#define ElemSize sizeof(SqList)   // 求结构体占用空间 

typedef char ElemType;  
typedef struct{
	ElemType *base;  // 栈底位置 
	ElemType *top;   // 栈顶位置 
	int size;        // 栈容量 
}SqList; 

/* 初始化栈 */ 
void initStack(SqList &S){
	S.base = (ElemType *)malloc(ElemSize * INITSIZE);   
	if(!S.base) exit(OVERFLOW);
	S.top = S.base;
	S.size = INITSIZE; 
}

/* 获取当前栈当前已用容量 */ 
int getLength(SqList S){
	return S.top - S.base; 
}

/* 判断栈是否空 */ 
bool isEmpty(SqList S){
	return getLength(S) == 0;
} 
/* 入栈 */ 
void push(SqList &S, ElemType e){
	if(getLength(S) >= S.size){ // 如果栈容量已满，则先扩容，再入栈 
		S.base = (ElemType *)realloc(S.base,ElemSize * (S.size + INCREMENTSIZE));
		if(!S.base) exit(OVERFLOW);
		S.top = S.base + S.size;  
		S.size += INCREMENTSIZE;
	}
	*(S.top++) = e;  // 入栈 
}

/* 出栈 */ 
bool pop(SqList &S, ElemType &e){
	if(isEmpty(S)) return false; // 栈空 
	e = *(--S.top);
	return true;
}

/* 输出传入的中缀表达式对应的后缀表达式 */ 
void changeMiddle2LastExpr(SqList S, ElemType *str){
	int i = 0;
	ElemType e;
	initStack(S);
	while(str[i] != '\0'){
		// + - 优先级最低 
		if(str[i] == '+' || str[i] == '-'){
			// 如果栈空，则 + - 直接入栈 
			if(isEmpty(S)) push(S,str[i]);
			// 栈不空，把栈中除 （ 以外的 优先级不低于 + - 的元素（* /）先出栈 
			else{
				do {
					pop(S,e);
					if(e == '(') push(S,e); // （ 特殊处理，除非遇到 ） ，否则 （ 不出栈 
					else cout << e << " ";
				}while(!isEmpty(S) && e != '('); 
				push(S, str[i]); // 当前符号入栈 
			}
		}
		/* * / 都是高优先级，（）对于 * / 来说不具有更高优先级 ， 可将 （ 与 * / 同等对待，*/ 
		/* 栈中已有符号优先级一定不会高于当前操作符 直接入栈即可 */ 
		else if(str[i] == '(' || str[i] == '*' || str[i] == '/'){
			push(S,str[i]);	
		}
		/* 遇到 ） 就一直出栈并输出，直到出栈的元素是 （ ，但 （ 不输出*/ 
		else if(str[i] == ')'){
			pop(S,e);
			while(e != '('){
				cout << e << " ";
				pop(S,e);
			}
		}
		/* 否则就是操作数，直接输出即可 */ 
		else {
			cout << str[i] << " ";
		}
		i++;
	}
	/* 最后把栈中剩余的运算符依次弹栈打印 */
	while(!isEmpty(S)){
		pop(S,e);
		cout << e << " ";
	}
	
}

int main(){
	
	SqList S;
	ElemType str[255];
	cout << endl << "Please input an Infix Expression: ";
	cin >> str;
	cout << endl << "The Postfix Expression is: ";
	changeMiddle2LastExpr(S, str);
	cout << endl;
	
	return 0;
}

运行结果如下

有问题欢迎指出！

打赏