將中綴表達式轉換爲後綴表達式 - 無效空間插入

Question

我製作了一個轉換器，它將中綴表達式轉換爲後綴表達式。

Example: 
Infix: 2 * 3 - 10/4 
Postfix: 2 3 * 10 4/- 

我有一個方法完全編碼，但它返回的後綴表達式是

2  3 * 1 0  4/- 

有兩個問題：1，主要問題是，他們是在1和之間的空間0，他們應該在一起時（10）。 2.有很多額外的空間，輸出應該看起來像上面提供的例子。

我已經完成了從infix到postfix的轉換研究，但我無法確定如何做更多的單個數字表達式轉換。

下面是附加到我的postfixtoinfix類，表達式變量包含在上面的示例中指示的中綴與完美的間距。

import java.util.*; 

public class InfixToPostfix 
{ 
//Declare Instance Variables 
private String expression; 
private Stack<Character> stack = new Stack<Character>(); 

//Constructor 
public InfixToPostfix(String infixExpression) 
{ 
     expression = infixExpression; 
}//End of constructor 

//Translate's the expression to postfix 
public String translate() 
{ 
    //Declare Method Variables 
    String input = ""; 
    String output = ""; 
    char character = ' '; 
    char nextCharacter = ' '; 

    for(int x = 0; x < expression.length(); x++) 
    { 
     character = expression.charAt(x); 

     if(isOperator(character)) 
     { 
      while(!stack.empty() && precedence(stack.peek())>= precedence(character)) 
       output += stack.pop() + " "; 
      stack.push(character); 
     } 
     else if(character == '(') 
     { 
      stack.push(character); 
     } 
     else if(character == ')') 
     { 
      while(!stack.peek().equals('(')) 
       output += stack.pop() + " "; 
      stack.pop(); 
     } 
     else 
     { 
      if(Character.isDigit(character) && (x + 1) < expression.length() && Character.isDigit(expression.charAt(x+1))) 
      { 
       output += character; 
      } 
      else if(Character.isDigit(character)) 
      { 
       output += character + " "; 
      } 
      else 
      { 
       output += character; 
      } 
     } 
    }//End of for 

    while(!stack.empty()) 
    { 
     output += stack.pop() + " "; 
    } 

    return output; 
}//End of translate method 

//Check priority on characters 
public static int precedence(char operator) 
{ 
    if(operator == '+' || operator =='-') 
     return 1; 
    else if(operator == '*' || operator == '/') 
     return 2; 
    else 
     return 0; 
}//End of priority method 

public boolean isOperator(char element) 
{ 
    if(element == '*' || element == '-' || element == '/' || element == '+') 
     return true; 
    else 
     return false; 
}//End of isOperator method 

}//End of class 

Answer 1

您的代碼沒有看到「10」作爲一個單一的實體，而是爲兩個單獨的字符，「1」和「0」。對於任何不是運營商或贊助商的人，您可以撥打output += character + " ";，這將給您的1 0而不是所需的10。

Answer 2

將任意算術表達式從其中綴（即常規算術表達式）轉換爲後綴形式的問題並不像起初可能出現的那樣簡單。

算術表達式表示一種上下文無關語言，可以使用下推自動識別來識別。作爲這種識別的結果，可以構建語法樹或AST（抽象語法樹），其將自下而上地構建後綴形式。

關於這個沒有太多理論的好實用書是Language Implementation Patterns，我強烈推薦。

Answer 3

就像@digitaljoel說的那樣，您將單個字符識別爲詞彙記號，而不是完整的單詞記號。

您應該讓解析器調用一個方法從輸入中讀取下一個完整標記，而不是讀取單個字符，然後確定它是什麼標記（操作符或操作數）。然後，令牌可以作爲字符串（包含一個或多個構成令牌的字符）或作爲類對象（包含令牌文本和某種類型的token_type屬性）返回。

否則，您的解析器僅限於處理單字符標記。

使用單獨的詞法分析器讀取令牌的另一個好處是可以在詞法分析器中而不是在解析器中處理空白。