Stack, Parentheses Matching

Question

So I'm working on some homework with PostFix and Infix Expressions. I'm running into a bit of a problem and can't seem to find where I'm having the issue. I can get the Infix to Postfix working...for the most part. Some of the equations I'm getting a ( or ) printed when I don't want it to be printed. Also when I have no matching parentheses I don't get an error like I want it to.

public String Infix(String equation) throws Exception{
    Stack stack=new Stack();
    boolean parensMatch=false;
    int priority=0;
    String temp="";
    for(int i=0; i<equation.length(); i++){
        char c=equation.charAt(i);
        //if the character is equal to left paren, push
        if(c=='('){
            stack.push(c);
        }
        //if the character is equal to right paren, we start popping until we find a match
        else if(c==')'){
            try{
                while(stack.peek()!='('){
                    temp+=stack.pop();
                }

                if(stack.peek()=='('){
                    char ch=stack.pop();
                    parensMatch=true;
                }

                if(parensMatch==false){
                    throw new Exception("Parens Not Match Error");
                }
            }catch(Exception e){
                System.out.println(e);
            }
            parensMatch=false;
        }
        //if the character is equal to an operator, we do some extra work
        //to figure out what is going to happen
        else if(c=='+' || c=='-' || c=='*' || c=='/' || c=='^'){
            char top=stack.peek();
            if(top=='^')
                priority=2;
            else if(top=='*' || top=='/')
                priority=1;
            else
                priority=0;
            if(priority==2){
                if(c=='*' || c=='/'){
                    temp+=stack.pop();
                }
                else if(c=='+' || c=='-'){
                    temp+=stack.pop();
                }
                else{
                    temp+=stack.pop();
                }
            }
            else{
                if(c=='*' || c=='/'){
                    temp+=stack.pop();
                    stack.push(c);
                }
                else if(c=='+' || c=='-'){
                    stack.push(c);
                }
                else{
                    stack.push(c);
                }
            }
        }
        //if the character is a space, we ignore it and move on
        else if(c==' '){
            ;
        }
        //if the character is a letter, we add it to the string
        else{
            temp+=c;
        }
    }
    int len = stack.size();
    for (int j = 0; j < len; j++)
       temp+=stack.pop();
    return temp;
}

This is my Infix to Postfix method

(((A + B) - (C - D)) / (E - F)) This is one of the expressions that I need to solve, and AB+CD--(EF-/ is what I get when it prints to the screen. ((A is another, this one should give me an error but A(( is printed to the screen.

I have been running the debug for quite a while and can't seem to get anywhere.

Any help would be very helpful. I know it has something to with the code posted but I can't find the logic error. Thanks in advance!

So I added a new function to help with matching parens that I think will be useful. It takes the equation and just counts to see if they match or not.

public static int matchingParens(String equation){
    int match=0;

    for(int i=0; i<equation.length(); i++){
        char c=equation.charAt(i);
        if(c=='(')
            match++;
        else if(c==')')
            match--;
        else
            ;
    }

    return match;
}

Answer 1

To validate if parenthesis are all matched up, you can run through your String input of the math expression with a counter of initial value of 0, and if you find a (, increment your counter by 1, and if you find a ), decrement your counter by 1. If the counter ever reaches -1, break out, as it isn't a valid parenthesis match. In the end, you should have the counter's value as 0. If not, you have a mismatched parenthesis.

For the infix to postfix case, here's a standard algorithm:

Define a stack
Go through each character in the string
If it is between 0 to 9, append it to output string.
If it is left brace push to stack
If it is operator *,+,- or / then 
          If the stack is empty push it to the stack
          If the stack is not empty then start a loop:
                             If the top of the stack has higher precedence
                             Then pop and append to output string
                             Else break
                     Push to the stack

If it is right brace then
            While stack not empty and top not equal to left brace
            Pop from stack and append to output string
            Finally pop out the left brace.