如何將前綴轉換爲中綴

Question

我很努力地理解將前綴表達式轉換爲中綴表達式的整個概念。

使用Prefix: -4/+1*327的表達式，是否會轉換爲4-1+3*2/7？

另一個例子也許Prefix: +-a*bc/de，會轉換爲a-b*c+d/e？

有沒有某種算法來使這個更簡單？

Answer 1

試試這個。

public class Prefix { 

    static final Map<String, Integer> PREC = new HashMap<>(); 
    static { PREC.put("+", 1); PREC.put("-", 1); PREC.put("*", 2); PREC.put("/", 2); } 

    static class Source { 
     final String s; 
     Source(String s) { this.s = s; } 
     int index = 0; 
     String token; 
     String next() { return token = index >= s.length() ? null : s.substring(index, ++index); } 
    } 

    static String parse(String s) { return parse(new Source(s), 0); } 

    static String parse(Source t, int prec) { 
     Integer self = PREC.get(t.next()); 
     if (self != null) { 
      String op = t.token; 
      String result = String.format("%s%s%s",parse(t, self), op, parse(t, self)); 
      if (self < prec) result = "(" + result + ")"; 
      return result; 
     } else 
      return t.token; 
    } 

    static void test(String prefix) { System.out.println(prefix + " -> " + parse(prefix)); } 

    public static void main(String[] args) { 
     test("-4/+1*327"); 
     test("+-a*bc/de"); 
     test("*-ab+cd"); 
    } 
} 

結果：

-4/+1*327 -> 4-(1+3*2)/7 
+-a*bc/de -> a-b*c+d/e 
*-ab+cd -> (a-b)*(c+d)