Creating a prefix notation expression

Question

I'm trying to change an expression to prefix notation. I was able to figure out postfix notation and I was wondering if it was possible to utilize the basic template of my postfix class when creating my prefix class. I'm wanting to take an expression like... (6 * ( 24 + 81)) and have an output of: * 6 + 24 81. Is this possible without keeping track of levels?...meaning do I need a tracking variable when my loop enters a parentheses part of the expression? I'm just having a hard time picturing how the structure works.

Here is my postfix code:

    static Stack operatorStack = new Stack();
String ConvertToPostfix(String exp) {
    exp = "("+exp+")";
    int i;
    char token;
    String output = "";

    for (i = 0; i < exp.length(); i++) {
        token = exp.charAt(i);
        if (Character.isLetterOrDigit(token) == true)
            output += token;
        else if (token == '(')
            operatorStack.push(token);
        else if (token == ')') {
            char topChar;
            while ((topChar = peekAtTop()) != '(') {
                output += topChar;
                popAtTop();
            }

        operatorStack.pop();
        } 
        else {
            while (priority(token) <= priority(peekAtTop())) {
                output += peekAtTop();
                popAtTop();
            }
            operatorStack.push(token);
        }
}
    return output;

}

Answer 1

Essentialy, the expressions are tree structures.

Here's a random illustration of this:

To change linear representation (that is, the expression as a string) you just change the way you traverse the tree. The Wikipedia article linked above contains all three examples.

What you need to do is:

• learn how to represent trees in Java (always handy);
• parse your expression into a tree (rather simple), StringTokenizer is your friend;
• translate the three traversal procedures to Java;
• call whatever procedure your professor would request. (BTW listening to the professor more won't hurt.)

Hope this helps!