大作業要求寫個中綴運算式轉后綴運算式，結果發現視頻里面給的解法是個錯的，網上找了一大堆，各種說法都有，公說公有理婆說婆有理，花里胡哨的，看著也復雜的一匹，說的話拐彎抹角的，看幾下就開始看不懂了，研究到凌晨終于畫了一張：秒殺大圖，圖是基于調度場演算法（Shunting-Yard algorithm）的流程圖，可以說是清晰明了，就照著圖無腦擼代碼就完事了
代碼如下（僅參考，建議還是看圖自己敲的舒服）：
public Queue infixToPostfix(Queue infix) {
Stack stack = new Stack();
Queue postfix = new Queue();
Boolean backtoRoot = false;
while (!infix.isEmpty()){
backtoRoot = false;
Data data = infix.poll();
if (data.type == Type.OPERATOR || data.type == Type.PAREN){
if ("+-*/".contains(data.getOperator() )){
while (!stack.isEmpty()) { //Stack is not empty
Token top = stack.peek();
if (("+-(".contains(top.getOperator()) & "/*".contains(data.getOperator())) | ((top.getOperator().equals("(")) & "-+".contains(data.getOperator() ))){ //堆疊頂元素優先級低于自己
stack.push(data);
backtoRoot = true;
break;
}else {
postfix.offer(stack.pop());
continue;
}
}
if (backtoRoot){
continue;
}
// Stack is empty
if (stack.isEmpty()){
stack.push(data);
continue;
}
continue;
}
if ((data.getOperator().equals("(") )){
stack.push(data);
continue;
}
if (")".contains(data.getOperator() )){
while (!stack.isEmpty() ){
if (stack.peek().getOperator().equals("(")) {
stack.pop();
break;
}
postfix.offer(stack.pop());
}
continue;
}
}
if (data.type == Type.OPERAND){
postfix.offer(data);
continue;
}
}
while (!stack.isEmpty()){
postfix.offer(stack.pop());
}
return postfix;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/180254.html
標籤：其他