I'm trying to create a program that converts infix expression to postfix (using stack) and evaluate the result of the postfix expression. I already have a solution that works, but I feel that it's ugly and that there must be a better approach.
(Note: the program must be able to accept digits greater than 9 and decimal number, so it's a bit more complicated than the usual converter)
Converter class:
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class PostFixConverter {
private String infix; // The infix expression to be converted
private Deque<Character> stack = new ArrayDeque<Character>();
private List<String> postfix = new ArrayList<String>(); // To hold the postfix expression
public PostFixConverter(String expression)
{
infix = expression;
convertExpression();
}
/* The approach is basically, if it's a number, push it to postfix list
* else if it's an operator, push it to stack
*/
private void convertExpression()
{
// Temporary string to hold the number
StringBuilder temp = new StringBuilder();
for(int i = 0; i != infix.length(); ++i)
{
if(Character.isDigit(infix.charAt(i)))
{
/* If we encounter a digit, read all digit next to it and append to temp
* until we encounter an operator.
*/
temp.append(infix.charAt(i));
while((i+1) != infix.length() && (Character.isDigit(infix.charAt(i+1))
|| infix.charAt(i+1) == '.'))
{
temp.append(infix.charAt(++i));
}
/* If the loop ends it means the next token is an operator or end of expression
* so we put temp into the postfix list and clear temp for next use
*/
postfix.add(temp.toString());
temp.delete(0, temp.length());
}
// Getting here means the token is an operator
else
inputToStack(infix.charAt(i));
}
clearStack();
}
private void inputToStack(char input)
{
if(stack.isEmpty() || input == '(')
stack.addLast(input);
else
{
if(input == ')')
{
while(!stack.getLast().equals('('))
{
postfix.add(stack.removeLast().toString());
}
stack.removeLast();
}
else
{
if(stack.getLast().equals('('))
stack.addLast(input);
else
{
while(!stack.isEmpty() && !stack.getLast().equals('(') &&
getPrecedence(input) <= getPrecedence(stack.getLast()))
{
postfix.add(stack.removeLast().toString());
}
stack.addLast(input);
}
}
}
}
private int getPrecedence(char op)
{
if (op == '+' || op == '-')
return 1;
else if (op == '*' || op == '/')
return 2;
else if (op == '^')
return 3;
else return 0;
}
private void clearStack()
{
while(!stack.isEmpty())
{
postfix.add(stack.removeLast().toString());
}
}
public void printExpression()
{
for(String str : postfix)
{
System.out.print(str + ' ');
}
}
public List<String> getPostfixAsList()
{
return postfix;
}
}
Calculator class:
import java.math.BigDecimal;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class PostFixCalculator {
private List<String> expression = new ArrayList<String>();
private Deque<Double> stack = new ArrayDeque<Double>();
public PostFixCalculator(List<String> postfix) {expression = postfix;}
public BigDecimal result()
{
for(int i = 0; i != expression.size(); ++i)
{
// Determine if current element is digit or not
if(Character.isDigit(expression.get(i).charAt(0)))
{
stack.addLast(Double.parseDouble(expression.get(i)));
}
else
{
double tempResult = 0;
double temp;
switch(expression.get(i))
{
case "+": temp = stack.removeLast();
tempResult = stack.removeLast() + temp;
break;
case "-": temp = stack.removeLast();
tempResult = stack.removeLast() - temp;
break;
case "*": temp = stack.removeLast();
tempResult = stack.removeLast() * temp;
break;
case "/": temp = stack.removeLast();
tempResult = stack.removeLast() / temp;
break;
}
stack.addLast(tempResult);
}
}
return new BigDecimal(stack.removeLast()).setScale(3, BigDecimal.ROUND_HALF_UP);
}
}
Here's some test run of the program:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class ConsoleCalc {
public static void main(String[] args) throws IOException
{
String expression;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter expression: ");
expression = br.readLine();
PostFixConverter pc = new PostFixConverter(expression);
System.out.print("Postfix: ");
pc.printExpression();
PostFixCalculator calc = new PostFixCalculator(pc.getPostfixAsList());
System.out.println();
System.out.println("Result: " + calc.result());
}
}
Result:
Enter expression: 10.2*(8-6)/3+112.5 Postfix: 10.2 8 6 - * 3 / 112.5 + Result: 119.300
I'm particularly concerned about the convertExpression method in the converter class. The way I read numeric token, digit by digit using a temporary StringBuilder is really ugly.
