Java 实例 - 利用堆栈将中缀表达式转换成后缀表达式
以下实例演示了如何使用堆栈进行表达式的堆栈将中缀(Infix)表达式转换成后缀(postfix)表达式:
InToPost.java 文件
importjava.io.IOException;
publicclassInToPost{privateStacktheStack;
privateStringinput;
privateStringoutput = "";
publicInToPost(Stringin){input = in;
intstackSize = input.length();
theStack = newStack(stackSize);
}publicStringdoTrans(){for(intj = 0; j < input.length(); j++){charch = input.charAt(j);
switch(ch){case'+':
case'-':
gotOper(ch, 1);
break;
case'*':
case'/':
gotOper(ch, 2);
break;
case'(':
theStack.push(ch);
break;
case')':
gotParen(ch);
break;
default:
output = output + ch;
break;
}}while(!theStack.isEmpty()){output = output + theStack.pop();
}System.out.println(output);
returnoutput;
}publicvoidgotOper(charopThis, intprec1){while(!theStack.isEmpty()){charopTop = theStack.pop();
if(opTop == '('){theStack.push(opTop);
break;
}else{intprec2;
if(opTop == '+' || opTop == '-')prec2 = 1;
elseprec2 = 2;
if(prec2 < prec1){theStack.push(opTop);
break;
}elseoutput = output + opTop;
}}theStack.push(opThis);
}publicvoidgotParen(charch){while(!theStack.isEmpty()){charchx = theStack.pop();
if(chx == '(')break;
elseoutput = output + chx;
}}publicstaticvoidmain(String[]args)throwsIOException{Stringinput = "1+2*4/5-7+3/6";
Stringoutput;
InToPosttheTrans = newInToPost(input);
output = theTrans.doTrans();
System.out.println("Postfix is " + output + '\n');
}classStack{privateintmaxSize;
privatechar[]stackArray;
privateinttop;
publicStack(intmax){maxSize = max;
stackArray = newchar[maxSize];
top = -1;
}publicvoidpush(charj){stackArray[++top] = j;
}publiccharpop(){returnstackArray[top--];
}publiccharpeek(){returnstackArray[top];
}publicbooleanisEmpty(){return(top == -1);
}}}
以上代码运行输出结果为:
124*5/+7-36/+ Postfix is 124*5/+7-36/+