Infix to Postfix Formula Parser Java

Question

I've written a program that takes a mathematical formula as an user input and converts it from infix to postfix.
It doesn't support negative numbers.
The program doesn't depend on the user having to pay attention on how to use spaces, so '1+2*3' and '1 + 2 * 3' are the same. (formulas like 'x^2^3' however must be written like 'x^(2^3)')
It provides support for the following operators: +, -, *, /, ^

Originally I had written a stack class completely myself, but this one (credits for stack class go to users of that post) is much more useful/reusable so I updated mine.

import java.util.EmptyStackException;
public class MyStack<T> {
 private T[] data;
 private int numElements;
 public MyStack(int capacity) {
 data = newArray(capacity);
 numElements = 0;
 }
 private final T[] newArray(int capacity) {
 @SuppressWarnings("unchecked")
 T[] tmp = (T[]) new Object[capacity];
 return tmp;
 }
 private void enlarge() {
 T[] temp = data;
 data = newArray(temp.length * 2);
 System.arraycopy(temp, 0, data, 0, temp.length);
 }
 public void push(T element) {
 if (numElements == data.length) {
 enlarge();
 }
 else {
 data[numElements++] = element;
 }
 }
 public T peek() {
 if (isEmpty()) {
 throw new EmptyStackException();
 }
 return data[numElements - 1];
 }
 public boolean isEmpty() {
 return (numElements == 0);
 }
 public T pop() {
 if (isEmpty()) {
 throw new EmptyStackException();
 }
 return data[--numElements];
 }
}

Here is the InfixToPostfixclass itself:

import java.util.Scanner;
public class InfixToPostfix {
 //checks whether c is operator
 private static boolean isOperator(char c) {
 if (c == '+' || c == '-' || c == '*' || c == '/' ||
 c == '^' || c == '(' || c == ')') {
 return true;
 }
 else return false;
 }
 //compares precedence of topmost operator in stack with operator at current position in infix-string
 private static boolean isLowerPrecedence(char operatorOldChar, char operatorNewChar) {
 boolean check = true; //true = new operator has higher precedence than old operator; false = contrary
 int operatorOld = 0, operatorNew = 0; //will compare precedence of operators; higher number = higher precedence
 //assign precedence to old operator (topmost in stack)
 if (operatorOldChar == '+' || operatorOldChar == '-') operatorOld = 2;
 else if (operatorOldChar == '*' || operatorOldChar == '/') operatorOld = 3;
 else if (operatorOldChar == '^') operatorOld = 4;
 //assign precedence to new operator (current character in infix)
 if (operatorNewChar == '+' || operatorNewChar == '-') operatorNew = 2;
 else if (operatorNewChar == '*' || operatorNewChar == '/') operatorNew = 3;
 else if (operatorNewChar == '^') operatorNew = 4;
 if (operatorNewChar == '(') {
 check = false;
 }
 else if (operatorNewChar == ')') {
 check = true;
 }
 else if (operatorOld < operatorNew) {
 check = false;
 }
 else if (operatorOld >= operatorNew) {
 check = true;
 }
 return check;
 }
 public static String convertToPostfix(String infix) {
 MyStack<Character> stack = new MyStack<>(infix.length());
 StringBuilder postfix = new StringBuilder();
 boolean isStillOneNumber = true; //will differentiate between outputs like 11 or 1 1
 for (int i = 0; i < infix.length(); i++) {
 if (!isOperator(infix.charAt(i)) & infix.charAt(i) != ' ') { //handles numbers and constants
 if (isStillOneNumber) {
 postfix.append(infix.charAt(i));
 }
 else {
 postfix.append(" ");
 postfix.append(infix.charAt(i));
 }
 isStillOneNumber = true;
 }
 else if (isOperator(infix.charAt(i))){ //handles operators
 if (infix.charAt(i) == ')') {
 while (!stack.isEmpty() & stack.peek() != '(') {
 postfix.append(" ");
 postfix.append(stack.pop());
 }
 if (!stack.isEmpty()) {
 stack.pop();
 }
 }
 else {
 if (!stack.isEmpty()) {
 if (!isLowerPrecedence(stack.peek(), infix.charAt(i))) {
 stack.push(infix.charAt(i));
 }
 else {
 while (!stack.isEmpty()) {
 postfix.append(" ");
 postfix.append(stack.pop());
 }
 stack.push(infix.charAt(i));
 }
 }
 else if (stack.isEmpty()) {
 stack.push(infix.charAt(i));
 }
 }
 isStillOneNumber = false;
 }
 else { //handles possible spaces in infix
 isStillOneNumber = false;
 }
 }
 while (!stack.isEmpty()) {
 postfix.append(" ");
 postfix.append(stack.pop());
 }
 return postfix.toString();
 }
 public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 System.out.print("Enter formula: ");
 String infix = scanner.nextLine();
 System.out.println(convertToPostfix(infix));
 }
}

I'd love to hear your opinions on my code!

Answer 1

Standard Stack

Try to use the standard implementation of a stack like java.util.ArrayDeque. You have reinvented the wheel here.

State Pattern

Introduce the state pattern. I here provide you an example.

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class NumberParser {
 public static void main(String[] args) {
 List<BigInteger> parse = new NumberParser(" 10 22 32 ").parse();
 for (BigInteger bigInteger : parse) {
 System.out.println(bigInteger);
 }
 }
 private List<BigInteger> numbers;
 private final StringBuffer stringToParse;
 private final StringBuffer buffer;
 private State state;
 public NumberParser(String string) {
 this.stringToParse = new StringBuffer(string);
 this.buffer = new StringBuffer();
 this.setState(new Unknown());
 }
 private boolean hasCurrentChar() {
 return this.stringToParse.length() > 0;
 }
 private char removeCurrentChar() {
 if (hasCurrentChar()) {
 char ch = this.stringToParse.charAt(0);
 this.stringToParse.deleteCharAt(0);
 return ch;
 } else {
 throw new NoSuchElementException();
 }
 }
 private char currentChar() {
 if (this.stringToParse.length() > 0) {
 return this.stringToParse.charAt(0);
 } else {
 throw new NoSuchElementException();
 }
 }
 private void clearBuffer() {
 buffer.setLength(0);
 }
 private void recognizeNumber() {
 numbers.add(new BigInteger(buffer.toString()));
 clearBuffer();
 }
 public List<BigInteger> parse() {
 if (numbers == null) {
 this.numbers = new ArrayList<>();
 while (!(getState() instanceof End)) {
 getState().parse();
 }
 }
 return this.numbers;
 }
 private State getState() {
 return state;
 }
 private void setState(State state) {
 System.out.println(state.getStateInfo());
 this.state = state;
 }
 private interface State {
 public String getStateInfo();
 public void parse();
 }
 private interface End extends State {
 }
 private class Error implements End {
 @Override
 public String getStateInfo() {
 return "Something went wrong ...";
 }
 @Override
 public void parse() {
 }
 }
 private class NoMoreChars implements End {
 @Override
 public String getStateInfo() {
 return "No chars left.";
 }
 @Override
 public void parse() {
 }
 }
 private class RemoveWhiteSpaces implements State {
 @Override
 public String getStateInfo() {
 return "Removing white spaces.";
 }
 @Override
 public void parse() {
 if (hasCurrentChar()) {
 if (Character.isWhitespace(currentChar())) {
 removeCurrentChar();
 } else {
 setState(new Unknown());
 }
 } else {
 setState(new NoMoreChars());
 }
 }
 }
 private class Number implements State {
 @Override
 public String getStateInfo() {
 return "Parse digits.";
 }
 @Override
 public void parse() {
 if (hasCurrentChar()) {
 if (Character.isDigit(currentChar())) {
 buffer.append(currentChar());
 removeCurrentChar();
 } else {
 recognizeNumber();
 setState(new Unknown());
 }
 } else {
 recognizeNumber();
 setState(new NoMoreChars());
 }
 }
 }
 private class Unknown implements State {
 @Override
 public String getStateInfo() {
 return "Search ...";
 }
 @Override
 public void parse() {
 if (hasCurrentChar()) {
 if (Character.isWhitespace(currentChar())) {
 setState(new RemoveWhiteSpaces());
 } else if (Character.isDigit(currentChar())){
 setState(new Number());
 } else {
 setState(new Error());
 }
 } else {
 setState(new NoMoreChars());
 }
 }
 }
}

This parser searches for numbers and returns them. Whitespaces separate numbers as whitespaces are allowed to occur multiple times. If you input alphanumeric characters the machine goes into the Error-State.

The main point is to avoid nested if-statements and have clear responsibilities during parsing. Furthermore your solution lacks extendability. If new requirements occur the state pattern helps you to manage them in a well-defined way.

First I suggest to have a state chart. UML state machines are appropriate.

• 200_success: java.util.Stack is based on the flawed Vector design of JDK 1.0. The documentation discourages its use in favour of ArrayDeque.
• oopexpert: Nevermind. The point was not reinventing the wheel. I adapted my answer to your hint.