Converting a Infix expression into a Postfix expre

Question

I am making a converter that will take infix expressions and convert them into postfix expressions.

Example:
Infix: 2 * 3 - 10 / 4
Postfix: 2 3 * 10 4 / -

I have a the method completely coded but the postfix expression it returns is

2     3   *   1 0     4 / -

There are two problems with this: 1. The major problem is that their is a space between the 1 and 0, when they should be together (10). 2. There are a lot of extra spaces, the output should look like the example provided above.

I have done research on converting from infix to postfix, but I couldn't determine how to do more then single digit expression conversions.

Below is attached my postfixtoinfix class, the expression variable holds the infix indicated in the example above with perfect spacing.

import java.util.*;

public class InfixToPostfix
{
//Declare Instance Variables
private String expression;
private Stack<Character> stack = new Stack<Character>();

//Constructor
public InfixToPostfix(String infixExpression)
{
        expression = infixExpression;
}//End of constructor

//Translate's the expression to postfix
public String translate()
{
    //Declare Method Variables
    String input = "";
    String output = "";
    char character = ' ';
    char nextCharacter = ' ';

    for(int x = 0; x < expression.length(); x++)
    {
        character = expression.charAt(x);

        if(isOperator(character))
        {
            while(!stack.empty() && precedence(stack.peek())>= precedence(character))
                output += stack.pop() + " ";
            stack.push(character);
        }   
        else if(character == '(')
        {
            stack.push(character);
        }
        else if(character == ')')
        {
            while(!stack.peek().equals('('))
                output += stack.pop() + " ";
            stack.pop();
        }
        else
        {
            if(Character.isDigit(character) && (x + 1) < expression.length() && Character.isDigit(expression.charAt(x+1)))
            {
                output += character;
            }
            else if(Character.isDigit(character))
            {
                output += character + " ";
            }   
            else
            {
                output += character;
            }
        }
    }//End of for

    while(!stack.empty())
    {
        output += stack.pop() + " ";
    }

    return output;
}//End of translate method

//Check priority on characters
public static int precedence(char operator)
{
    if(operator == '+' || operator =='-')
        return 1;
    else if(operator == '*' || operator == '/')
        return 2;
    else
        return 0;
}//End of priority method

public boolean isOperator(char element)
{
    if(element == '*' || element == '-' || element == '/' || element == '+')
        return true;
    else
        return false;
}//End of isOperator method

}//End of class

Answer 1

Your code is not seeing "10" as a single entity, but rather as two separate characters, '1', and '0'. For anything that isn't an operator or parens you do output += character + " "; which is going to give you your 1 0 instead of the desired 10.

Answer 2

Like @digitaljoel said, you are recognizing individual characters as lexical tokens, instead of complete words as tokens.

Instead of reading a single character and then deciding what token (operator or operand) it is, you should be having the parser call a method to read the next complete token from the input. The token can then be returned as a string (containing one or more characters comprising the token), or as a class object (containing the text of the token, and some kind of token_type property).

Otherwise, your parser is limited to handling only single-character tokens.

Another benefit of using a separate lexical analyzer to read tokens is that you can handle whitespace in the lexer instead of in the parser.

Answer 3

The problem of converting an arbitrary arithmetic expression from its infix from (i.e. conventional for arithmetic expression) to a postfix form is not as simple as it might appear at first.

Arithmetic expressions represent a context free language, which can be recognised using a pushdown automation. As the result of such recognition a syntax tree or an AST (abstract syntax tree) could be constructed, which would be walked bottom-up in order to construct an postfix form.

A good practical book on this without too much of the theory is Language Implementation Patterns, which I highly recommend.