AlgorithmsInJava/DataStructures/Stacks/InfixToPostfix.java at master · csbase/AlgorithmsInJava

55 lines (51 loc) · 1.47 KB

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;
    }
  }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Expand file tree

Search code, repositories, users, issues, pull requests...

Uh oh!

FilesExpand file tree

InfixToPostfix.java

Latest commit

History

InfixToPostfix.java

File metadata and controls

Expand file tree