How to create Postfix notation using stacks?

Question

I've been coding a class that takes a string input and then converts it into postfix notation. For some reason I cannot seem to find a bug that I have. Everything seems to work ok until the couple of last test cases that I run.

My input test case: (a*(b+c)-(d-e)/f) *g/(h-i)-j *k

My expected output test case: abc+*de-f/-g*hi-/jk*-

My output case: abc+de-f/-*ghi-jk*-/*

I've been looking at my code for like 2 hrs trying different things to fix the problem, but I still can't seem to find what the problem is. If someone could help me with identifying the problem, I would greatly appreciate it.

Here's the class:

import java.util.Stack;

public class InfixToPostfixConverter
{
//**********************************************************************
//The precedence method determines the precedence between two operators.
//If the first operator is of higher or equal precedence than the second
//operator, it returns the value true, otherwise it returns false.
//***********************************************************************
public static boolean precedence(char topStack, char currentChar)
{
   if(topStack == '*' || topStack == '/'){
       if(currentChar == '+' || currentChar == '-'){
           return true;
       }
   }
   else if(topStack == currentChar){
       return true;
   }
   else if(topStack == '+' && currentChar == '-'){
      return true;
   }
   else if(topStack == '-' && currentChar == '+'){
      return true;
   }
   else if(topStack == '*' && currentChar == '/'){
       return true;
   }
   else if(topStack == '/' && currentChar == '*'){
       return true;
   }

   return false;
}
char currentChar = infixString.charAt(i);

    //Case A:
     if(currentChar != '+' && currentChar != '-' && currentChar != '*' && currentChar != '/' && currentChar != '(' && currentChar != ')' ){
         postfixString += currentChar;
     }

    //Case B:
     else if(currentChar == '('){
         stack1.push(currentChar);
     }

    //Case C:
     else if(stack1.isEmpty() && currentChar == '+' || currentChar == '-' || currentChar == '*' || currentChar == '/'){
         stack1.push(currentChar);
     }

    //Case D:
     else if(currentChar == '+' || currentChar == '-' || currentChar == '*' || currentChar == '/' && !stack1.isEmpty()){
         char topStack = stack1.peek();

        while(!stack1.isEmpty()){
            if(precedence(topStack, currentChar)){
                postfixString += stack1.pop();
            }
            else{
                stack1.push(currentChar);
                break;
            } 

        }



     }

    //Case E:
     else if(currentChar == ')' && !stack1.isEmpty()){
         while(!stack1.isEmpty() && stack1.peek() != '('){
             postfixString += stack1.pop();
         }
         stack1.pop();
     }


  } //end of for loop


    //Case F:
  if(!stack1.isEmpty() && stack1.peek() == '('){
      return "No matching close parenthesis error.";
  }
  else if(!stack1.isEmpty() && stack1.peek() != '('){
      while(!stack1.isEmpty() && stack1.peek() != '('){
          postfixString += stack1.pop();
      }
  }


  return postfixString;


}//end of convertToPostfix method

}//end of the InfixToPostfixConverter class

I think your input case is missing operators in front of g and k? — John Vinopal, Nov 17 '15 at 22:21
Have you stepped through in debug to see why your algorithm decides to output `d` instead of `*`? I would think a debugger would be quick to show which condition is flawed. — digitaljoel, Nov 17 '15 at 22:43
Try a simpler test case like 'a\*b+c'. This yields 'ab\*c' which is a bug in case D. — John Vinopal, Nov 17 '15 at 22:55
I'm also a little suspicious of your precedence method. It looks like precedence('+','+') returns false which is contrary to the documentation. — John Vinopal, Nov 17 '15 at 22:58
`precedence ('*', '+')` and friends also return true, which is incorrect. — user207421, Nov 17 '15 at 23:16
@EJP How is that incorrect? If the first parameter has higher precedence than the second value, it returns true. * has higher precedence than + doesn't it? — Suds2, Nov 17 '15 at 23:25

How to create Postfix notation using stacks?

0 Answers0