Coder Joe Coder Joe - 14 days ago 8
Java Question

Infix-->Postfix Parantheses not being handled correctly Java

Attempting to reverse engineer some code I found via Googling. So far, I've managed to take code that didn't support modulus or floating point numbers and made it do so. However, I'm attempting to add support for parentheses and I'm stuck. I'm comparing the code I have in front of me to the correct solution and I'm not sure why mine is not working -- to me, it looks identical.

Current code:

import java.util.StringTokenizer;
import java.util.Stack;


public class calculatorPractice {

static int precedenceOrder(char op) {
switch (op) {

case '(':
return 3;
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
default: return 0;

}
}


public static boolean isSpace(char c){
return (c == ' ');
}



public static boolean decidePrecedence(char a, char b){
return (precedenceOrder(a) >= precedenceOrder(b));
}


public static String infixToPostfix(String infix) {
StringTokenizer t = new StringTokenizer(infix);
String postfix = "";
Stack opStack = new Stack();

while (t.hasMoreTokens()) {
String token = t.nextToken();
char c = token.charAt(0);

if(c == '('){
opStack.push(c);
}
else if (Character.isDigit(c)) {
postfix += (token + " ");
}
else if (c == ')'){
while(!opStack.isEmpty()
&& opStack.peek() != '(' ){

postfix += (opStack.pop() + " ");
}
while(!opStack.isEmpty()) {
opStack.pop(); //DOES NOTHING?
}
}

else {
char topElement;
while (!opStack.empty() && (decidePrecedence((Character) opStack.peek(), c)) ){
topElement = (Character) opStack.pop();
if(topElement != '('){
postfix += (topElement + " ");
}
}

opStack.push(new Character(c));

}
}


while (!opStack.empty()) {
char top = (Character)opStack.pop();
postfix += (top + " ");
}
return postfix;
}





public static boolean isOperator(char c) {

return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
|| c=='(' || c==')' || c == '%';
}






public static double evalPostfix(String postfix) {

postfix = postfix.replace(" ","");

StringTokenizer t = new StringTokenizer(postfix);
Stack opStack = new Stack();
String token;
double op1, op2, result = 0;

while (t.hasMoreTokens()) {
token = t.nextToken();
char c = token.charAt(0);
if (isOperator(c)) {
op2 = (Double) opStack.pop();
op1 = (Double) opStack.pop();

result = evalSingle(c, op1, op2);
opStack.push(new Double(result));
}
else {
double pushValue = Double.valueOf(String.valueOf(c));
opStack.push(pushValue);
}
}

result = (Double) opStack.pop();

if(!opStack.isEmpty()){
throw new IllegalArgumentException("invalid postfix");
}
return result;
}



public static double evalSingle(char op, double op1, double op2) {

double rightVal = op1;
double leftVal = op2;
double result;

switch (op) {
case '+': result = leftVal + rightVal; break;
case '-': result = leftVal - rightVal; break;
case '*': result = leftVal * rightVal; break;
case '/': result = leftVal / rightVal; break;
case '%': result = leftVal % rightVal; break;
default:
throw new IllegalArgumentException("invalid postfix");
}
return result;
}











public static void main1(String[] args) {
String infix = args[0];
String postfix = infixToPostfix(infix);
System.out.println("postfix: " + postfix);
Double value = evalPostfix(postfix);
System.out.println("value: " + value);
}
}


I am attempting to pass in the argument: "5 * ( ( 9 + 8 ) % 3 ) + 2 * 2"

The correct postfix is (I'm pretty sure, did it by hand): "5 9 8 + 3 % * 2 2 * + "

The postfix I am currently getting is: "5 9 * 8 + 3 % 2 2 * + "

As you can see, the issue is definitely with the last piece of code I attempted to add. The issue is that the "*" operator needs to be moved to its correct location, next to the "%" sign. I am not sure why it isn't being handled correctly.

Perhaps the line "opStack.pop(); //DOES NOTHING?" is indicative of the problem? I'm at a loss...

Thank you for your help!

References:

http://m.smithworx.com/cs235/notes/view.php?file=extra%20notes/rodham/09-stacks/Calculator.java

https://gist.github.com/deepshah22/7003555

http://codereview.stackexchange.com/questions/59565/infix-to-postfix-converter-program

Answer

Corrected portion of the code -

static int precedenceOrder(char op) {
        switch (op) {

        case '(':
            return -1;  // Changed from 3 to -1
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
        case '%':
            return 2;
        default:
            return 0;

        }
    }

    public static boolean isSpace(char c) {
        return (c == ' ');
    }

    public static boolean decidePrecedence(char a, char b) {
        return (precedenceOrder(a) >= precedenceOrder(b));
    }

    public static String infixToPostfix(String infix) {
        StringTokenizer t = new StringTokenizer(infix);
        String postfix = "";
        Stack opStack = new Stack();

        while (t.hasMoreTokens()) {

            String token = t.nextToken();
            char c = token.charAt(0);

            System.out.println("Stack :" + opStack);
            System.out.println("Token - " + c );

            if (c == '(') {
                opStack.push(c);
            } else if (Character.isDigit(c)) {
                postfix += (token + " ");
            } else if (c == ')') {
                while (!opStack.isEmpty() && !opStack.peek().equals('(')) {
                    postfix += (opStack.pop() + " ");
                }
                if (!opStack.isEmpty()) { // Changed from while to if.
                    opStack.pop(); // DOES NOTHING? Removes ( from stack.
                }
            }
            else {
                char topElement;
                while (!opStack.empty() && (decidePrecedence((Character) opStack.peek(), c))) {
                    topElement = (Character) opStack.pop();
                    if (topElement != '(') {
                        postfix += (topElement + " ");
                    }
                }

                opStack.push(new Character(c));
            }
        }

        while (!opStack.empty()) {
            char top = (Character) opStack.pop();
            postfix += (top + " ");
        }
        return postfix;
    }