package DataStructures.Stacks;

import java.util.Stack;

public class InfixToPostfix {
 public static void main(String[] args) throws Exception {
 assert "32+".equals(infix2PostFix("3+2"));
 assert "123++".equals(infix2PostFix("1+(2+3)"));
 assert "34+5*6-".equals(infix2PostFix("(3+4)*5-6"));
 }

 public static String infix2PostFix(String infixExpression) throws Exception {
 if (!BalancedBrackets.isBalanced(infixExpression)) {
 throw new Exception("invalid expression");
 }
 StringBuilder output = new StringBuilder();
 Stack<Character> stack = new Stack<>();
 for (char element : infixExpression.toCharArray()) {
 if (Character.isLetterOrDigit(element)) {
 output.append(element);
 } else if (element == '(') {
 stack.push(element);
 } else if (element == ')') {
 while (!stack.isEmpty() && stack.peek() != '(') {
 output.append(stack.pop());
 }
 stack.pop();
 } else {
 while (!stack.isEmpty() && precedence(element) <= precedence(stack.peek())) {
 output.append(stack.pop());
 }
 stack.push(element);
 }
 }
 while (!stack.isEmpty()) {
 output.append(stack.pop());
 }
 return output.toString();
 }

 private static int precedence(char operator) {
 switch (operator) {
 case '+':
 case '-':
 return 0;
 case '*':
 case '/':
 return 1;
 case '^':
 return 2;
 default:
 return -1;
 }
 }
}