Title: Stack Parenthesis Checker ... Help for MP6
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Stack Parenthesis Checker ... Help for MP6

- Stacks can be used to solve many problems. It's amazing that such a simple class can be so useful.
- In MP6, you will create a program to check for proper indentation using a stack. In this lecture, I am creating a program to check for proper matching of parenthesis. Although this is a different problem, it shares some common techniques with the MP6 problem.

Stack<T>( ) - constructor

boolean empty( ) - check to see if the stack is empty

T peek( ) - Look at the top of the stack

T pop( ) - Pop the top of the stack

T push ( T item) - push an item on the stack (returns item pushed ... usually we ignore this return)

Problem statement: We will check program files to make sure that every left hand paren : ( , {, [ has an appropriate matching ], }. )

See the examples below in the test files that we will run.

ParenthesisChecker.java


import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;

class ParenthesisException extends RuntimeException
{
    ParenthesisException(String error)
    {
        super(error);
    }
}

class ParenData
{
    private char leftParen;
    private int lineNumber,  charLocation;

    public ParenData(char leftParen, int lineNumber, int charLocation)
    {
        this.leftParen = leftParen;
        this.lineNumber = lineNumber;
        this.charLocation = charLocation;
    }

    public String getLeftLocation()
    {
        return "left side(" + leftParen + ") at line: "+lineNumber + " charLocation: "+ charLocation;
    }

    public boolean checkRightParen(char rightParen)
    {
        boolean good_match= false;
        switch (rightParen)
        {
        case '}':
            if (leftParen == '{')
                good_match = true;
            break;

        case ')':
            if (leftParen == '(')
                good_match = true;
            break;

        case ']':
            if (leftParen == '[')
                good_match = true;
            break;

        }
        return good_match;
    }

}

public class ParenthesisChecker {

    private Stack<ParenData> parenStack = new Stack<ParenData>();

    public void checkParens(String fileName)
    {
        Scanner input=null;
        parenStack.clear();
        try {
            input = new Scanner( new File(fileName));
            int lineNumber = 1;
            while (input.hasNextLine())
            {
                String line = input.nextLine();
                System.out.println(lineNumber+":"+ line);

                processLine(line, lineNumber);

                lineNumber += 1;
            }
            if (parenStack.isEmpty())
                System.out.println(fileName +" has proper paren syntax");
            else
            {
                while (!parenStack.isEmpty())
                {
                    ParenData pdTop = parenStack.peek();
                    System.out.println("Unmatched: " + pdTop.getLeftLocation());
                    parenStack.pop();
                }
            }
        }
        catch (ParenthesisException error)
        {
            System.out.println(error);
        }
        catch (FileNotFoundException e)
        {
            System.out.println("Unable to open: " + fileName);
        }
        finally
        {
            if (input != null)
                input.close();
        }
    }

    private void processLine(String line, int lineNumber)
    {
        for (int charLocation=0; charLocation < line.length(); charLocation++)
        {
            char parenChar = line.charAt(charLocation);
            switch (parenChar)
            {
            case '{':
            case '(':
            case '[':
                ParenData pd = new ParenData(parenChar, lineNumber, charLocation);
                parenStack.push( pd );
                break;

            case '}':
            case ')':
            case ']':
                if (parenStack.isEmpty())
                {
                    String error1 = "Empty Stack when "+parenChar +
                            " encountered at lineNumber:"+lineNumber+ " char location: "+ charLocation;
                    throw new ParenthesisException(error1);
                }
                else
                {
                    ParenData pdTop = parenStack.peek();
                    if (pdTop.checkRightParen(parenChar))
                        parenStack.pop();
                    else
                    {
                        String error2 = "Paren Mismatch ... found "+ parenChar +
                                " lineNumber:"+lineNumber+ " char location: "+ charLocation +
                                " does not match: " + pdTop.getLeftLocation();
                        throw new ParenthesisException(error2);
                    }

                }

                break;
            }
        }
    }

    public static void main(String[] args) {
        ParenthesisChecker parenChecker = new ParenthesisChecker();

        for (int i=0; i < args.length; i++)
        {
            System.out.println("Processing file: " + args[i]);
            parenChecker.checkParens(args[i]);
        }

    }

}



goodParens.txt


Program()
{
    x=y[f(x,y)];
    if (y[1] == f(x,y))
    {
        x =(8+2*((4+6)*(7+x[9])+2));
    }
    else
    {
        {{(([[]]))}} // try to break things
    }
}


badParens.txt


Program()
{
    x=y[f(x,y)];
    if (y[1] == f(x,y))
    {
        x =(8+2*((4+6)*(7+x[9])+2); // MISSING ending Right Paren
    }
    else
    {
        {{(([[]]))}} // try to break things
    }
}


Last Updated: March 10, 2014 0:38 AM