Implementation of Stack for Checking Incorrect Braces Used to Validate HTML Source Code in Java

HTML is a page-format language which is used to format how an internet browser should deliver a content to the user. HTML (and CSS) is not really a programming language. However, HTML is important here for illustration of how stack can be used to detect mismatch opening-closing braces.

Imagine there is an invalid HTML code:

<HTML><BODY><p)Hello World(/p></BODY}</HTML}>

The code is incorrect as many of the tags are opened or closed with wrong character. Often, in a sensitive programming languages like C/C++/Java/VisualBasic, mismatch symbol can cause a thousand lines of code to fail compiled. A good compiler can identify at which line and which row is the mismatches occurs. We will develop something like that in Java.

The Classes

We will create 2 classes inside 1 classes:

  • ParenthesisChecker
  • static Stack

The Code

public class ParenthesisChecker 
{
    static class Stack<E>
    {
    ArrayList<E> arr;
    int nElems;

    public Stack()
    {
        arr = new ArrayList<E>();
        nElems = 0;
    }

    public void push(E c)
    {
        arr.add(nElems++, c);
    }

    public E pop()
    {
        E e = this.peek();
        this.removeLast();
        return e;
    }

    public E peek()
    {
        E e = arr.get(nElems - 1);
        return e;
    }

    public void removeLast()
    {
        arr.remove(nElems-1);
        nElems--;
    }

    public boolean isEmpty()
    {
        return (this.nElems == 0);
    }

    public void printAll()
    {
        for (int i=0; i<nElems; i++)
        {
        System.out.println("" + i + ": " + arr.get(i));
        }
    }
    }

    public static void main(String[] args)
    {
    Stack<Character> s = new Stack<Character>(); //keep tracking of symbol character
    Stack<Integer> p = new Stack<Integer>(); //keep tracking of position

    String GOMS = "<HTML><BODY><p)Hello World(/p></BODY}</HTML}>";

    //check
    for (int i=0; i<GOMS.length(); i++)
    {
        char c = GOMS.charAt(i);
        switch (c)
        {
        case '(':
        case '[':
        case '{':
        case '<':
            s.push(c);
            p.push(i);
            break;
        case ')':
        case ']':
        case '}':
        case '>':
            if (s.isEmpty())
            System.out.println("Error. No match opening symbol for " + c + " @" + i);
            else
            {
            char popped = s.pop(); //the popped character from stack
            if (popped == '(' && c == ')')
            {}
            else if (popped == '[' && c == ']')
            {}
            else if (popped== '{' && c == '}')
            {}
            else if (popped== '<' && c == '>')
            {}
            else
            {
                //error... mismatch close 
                System.out.println("Mismatch close " + c + " for opening " + popped + " @" + p.pop());
            }

            }
        }
    }
    }
}

Explaination

static Stack class

The static class, as it is static, is defined within a main class which is the ParenthesisChecker.java. We are implementing Generics here, so we can reuse this class for any data type. Actually this stack class is not different from the basic Stack class we discuss here.

ParenthesisChecker class

This is the main class, and the center of discussion here.

We are creating two objects of Stack, which are:

  • p which describes the position of where the error occurs. it is of type Integer-tailored Stack
  • s which describes the opening parenthesis. it is of type Character-tailored Stack.

Remember: as Java from version 5 support autoboxing, we can use wrapper class instead of its primitive type as we are working with ArrayList that only support abstract data type.

We start the algorithm at the for-loop block. Before going to the main code, here is the algorithm.

  1. Go through the String.
  2. If found opening, push into stack.
  3. If found closing, pop stack and match the braces.
  4. If the braces not match, it is error.
  5. Else it is okay.
char c = GOMS.charAt(i);
        switch (c)
        {
        case '(':
        case '[':
        case '{':
        case '<':
            s.push(c);
            p.push(i);
            break;

Now see that part of code. char c is defined to fetch character in a String at position i. This ‘c’ character only be responded by the algorithm if this is either one of the 8 cases switch.

  • It will be push into the stack if it is opening.
  • It will be compared if it is closing
case ')':
        case ']':
        case '}':
        case '>':
            if (s.isEmpty())
            System.out.println("Error. No match opening symbol for " + c + " @" + i);
            else
            {
            char popped = s.pop(); //the popped character from stack
            if (popped == '(' && c == ')')
            {}
            else if (popped == '[' && c == ']')
            {}
            else if (popped== '{' && c == '}')
            {}
            else if (popped== '<' && c == '>')
            {}
            else
            {
                //error... mismatch close 
                System.out.println("Mismatch close " + c + " for opening " + popped + " @" + p.pop());
            }

Nah. After founding a closing brace, we compare it. We define char popped to be a popped character from the Stack, it always be a opening brace. After get the popped character, and compare it, if nothing wrong, then do nothing. If there is mistake, we report the mismatch.

Now, you should understand about p.pop(). I wouldn’t go to explain it. Take a break, and think about it as it is a quite trivial coding. However, there would be some error in this code (or algorithm), if you found out, yes you can change it because I just finished coding, not examining for bug, and directly posted to this. Hopefully, there is not bug.

Thank you. Hope this helps 🙂

Advertisements

One thought on “Implementation of Stack for Checking Incorrect Braces Used to Validate HTML Source Code in Java

  1. actually. you can implement this technique to check whether the <html> has its closing </HTML> the <p> and </p> and that makes the program more complex. you can create that, however.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s