5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Some of your functions contain too many loops and branchings; try to use more separate functions (e.g. for the switch block, or for reading a number). When you read a number, increase an index and copy the whole thing at once; don't fiddle around with single digits. Avoid 'else if' and don't increment within a function call (e.g., 'function(i++)'). PS: If you want more compact code, you can replace the precedence function by "+-*/^".indexOf(op) \$\endgroup\$ – Chris Aug 17 '15 at 10:39
1
\$\begingroup\$

What is common in parsers is to separate the lexical tokenizing part from the semantic grammatical analysis. You can see this in unix parser tools, which have lexical tools flex/lex and parser tools bison/yacc.

I would consider a greater separation in your code. Create a new Token class to hold the individual tokens and a new Tokenizer class, whose job is the split the input into a list of tokens. The parser will then process the list of tokens and generate the stack. This allows the bugs to be identified easier, is the bug in the lexing part or the gramatical parsing. It will also make expansion of the code much easier.

In my code I have different sub-classes of Token for numbers, operators variable names etc. I've used Regular Expressions to match the different types of token. I use (\d+\.?\d*)|(\.\d+) to match numbers. \d matches a single digit, \d+ matches one or more decimal digits, \d* matches zero or more digits, \. matches a literal decimal point, \.? matches an optional decimal point, ( and ) groups a sub-pattern together and | matches either the lhs or rhs. So the lhs will match either a set of digits with no decimal place or a set of digits followed by decimal place with optional digits afterwards. The rhs will match a decimal place followed by a set of digits. This mean the whole regexp will match 123, 123., 123.45, .45.

\$\endgroup\$
  • \$\begingroup\$ Separating the code using Token and Tokenizer class seems like a good idea. I'll work it out later, thanks for the feedback! \$\endgroup\$ – Heisenberg Aug 17 '15 at 13:40
  • \$\begingroup\$ By the way can you explain more about using Regular Expression to match numbers? I'm not familiar with regex \$\endgroup\$ – Heisenberg Aug 17 '15 at 14:07
  • \$\begingroup\$ I've expanded the details of the specific number regexp. Its a big topic a fair place to start is Java Tutorial Leason on Regular Expressions \$\endgroup\$ – Salix alba Aug 17 '15 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.