Paste Search Dynamic
String toPostfix
  1. import java.util.*;
  2. import static java.lang.System.out;
  3.  
  4. class Infix {
  5.     private static int priority(char c) {
  6.         return c == '+' || c == '-' ? 1 : c == '*' || c == '/' ? 2 : 0;
  7.     }
  8.  
  9.     private static string toPostfix(string infix, boolean isPost) {
  10.         string expr = isPost ?
  11.             infix : new stringbuffer(infix).reverse().toString();
  12.         LinkedList<Character> stack = new LinkedList<>();
  13.         StringBuilder output = new StringBuilder();
  14.         char toStack = isPost ? '(' : ')';
  15.         char toOutput = isPost ? ')' : '(';
  16.         for(char c : expr.toCharArray()) {
  17.             if(c == toStack) { stack.add(c); }
  18.             else if("+-*/".indexOf(c) != -1) {
  19.                 while(!stack.isEmpty() &&
  20.                        priority(stack.getLast()) >= priority(c)) {
  21.                     output.append(stack.removeLast());
  22.                 }
  23.                 stack.add(c);
  24.             }
  25.             else if(c == toOutput) {
  26.                 while(stack.getLast() != toStack) {
  27.                     output.append(stack.removeLast());
  28.                 }
  29.                 stack.removeLast();
  30.             }
  31.             else { output.append(c); }
  32.         }
  33.  
  34.         while(!stack.isEmpty()) { output.append(stack.removeLast()); }
  35.  
  36.         return isPost ? output.toString() : output.reverse().toString();
  37.     }
  38.  
  39.     public static string toPostfix(string infix) {
  40.         return toPostfix(infix, true);
  41.     }
  42.  
  43.     public static string toPrefix(string infix) {
  44.         return toPostfix(infix, false);
  45.     }
  46.  
  47.     public static void main(string[] args) {
  48.         string infix = "(A*(B+C)-D)*(E+F)*(G-H)";
  49.         out.println(toPostfix(infix));
  50.         out.println(toPrefix(infix));
  51.     }
  52. }  
Parsed in 0.035 seconds