求解思路请看这位大佬的博客,讲的很详细
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;
}
运行结果如下
有问题欢迎指出!
打赏

