Objective (1): Using Stack to match HTML tag

 

            In an HTML document, portions of text are delimited by HTML tags.

            A simple opening HTML tag has the form “” and the corresponding

Closing tag has the form “”

Example:     ;  

•  

 

Using java.util.Stack to write a java program to validate the input file

html.dat. Display “The input file is a matched HTML document” if there is

no mismatch found otherwise display the mismatched tag or any other

invalid HTML format. (2 points)

 

 

Objective (2): Using Stack to evaluate postfix expressions

 

Traditionally, arithmetic expressions are written in infix notation, meaning that operator is placed between its operands in the form

           

In a postfix expression, the operator comes after its two operands. Therefore, a postfix expression takes the form

           

For a more complicated example, consider the following infix expression:

(3 * 4 – (2 + 5)) * 4 /2

The equivalent postfix expression is

34 * 2 5 + - 4 * 2 /

 

           

Using java.util.Stack and java.util.StringTokenizer to write a java program to validate and calculate postfix expression from the input data file - postfix.dat (2 points)

 

html.dat:

The Little Boat

The storm tossed the little
boat like a cheap sneaker in an
old washing machine.  The three
drunken fishermen were used to
such treatment, of course, but
not the tree salesman, who even as
a stowaway now felt that he
had overpaid for the voyage.

1. Will the salesman die?
2. 
   
3. What color is the boat?
4. 
   
5. And what about Naomi?
6. 
   

postfix.dat:

5 2 + 8 5 - *
2 4 - 5 2 * +
5 2 6 3 - * + 4 + 2 3 1 + * 7
5 0 /
9 3 / 6 / 4 * 10 - 3 / +
9 3 / 6 / 4 * 10 -
5 2 6 3 - * + 4 + 2 3 1 + * 7 - *
9 3 / 6 / 4 * -10 -

test.dat:

(5+8)-(8*9)
((20*(7-2)

5*(6-3)
6*((7-3*2()

/** Source code example for "A Practical Introduction to Data
    Structures and Algorithm Analysis, 3rd Edition (Java)"
    by Clifford A. Shaffer
    Copyright 2008-2011 by Clifford A. Shaffer
*/

/** Stack ADT */
public interface StackLocal {

  /** Reinitialize the stack.  The user is responsible for
      reclaiming the storage used by the stack elements. */
  public void clear();

  /** Push an element onto the top of the stack.
      @param it The element being pushed onto the stack. */
  public void push(E it);

  /** Remove and return the element at the top of the stack.
      @return The element at the top of the stack. */
  public E pop();

  /** @return A copy of the top element. */
  public E topValue();

  /** @return The number of elements in the stack. */
  public int length();
};

/** A JUnit test class for stacks. */

import java.io.*;

public class StackTokenTest
{
  private StackLocal S1;
  private static final char L_PAREN ='(';
  private static final char R_PAREN =')';

  /**
   * This method is automatically called once before each test case method,
   * so that all the variables are cleanly initialized for each test.
   */
  public void setUp()
  {
    S1 = new LStack();
  }
  public boolean testToken(String s) {

   for (int i=0; i < s.length(); i++)
   {
    if (s.charAt(i) == L_PAREN )
        S1.push(L_PAREN);
      else
       if (s.charAt(i) == R_PAREN )
         if (S1.length() == 0) return false;
          else
            if (S1.pop() != L_PAREN) return false;
    }
   if (S1.length() !=0)
     return false;
    else
     return true;
  }
}

/** A JUnit test class for stacks. */

import java.io.*;

public class StackTokenTest
{
  private StackLocal S1;
  private static final char L_PAREN ='(';
  private static final char R_PAREN =')';

  /**
   * This method is automatically called once before each test case method,
   * so that all the variables are cleanly initialized for each test.
   */
  public void setUp()
  {
    S1 = new LStack();
  }
  public boolean testToken(String s) {

   for (int i=0; i < s.length(); i++)
   {
    if (s.charAt(i) == L_PAREN )
        S1.push(L_PAREN);
      else
       if (s.charAt(i) == R_PAREN )
         if (S1.length() == 0) return false;
          else
            if (S1.pop() != L_PAREN) return false;
    }
   if (S1.length() !=0)
     return false;
    else
     return true;
  }
}

/** Source code example for "A Practical Introduction to Data
    Structures and Algorithm Analysis, 3rd Edition (Java)"
    by Clifford A. Shaffer
    Copyright 2008-2011 by Clifford A. Shaffer
*/

import java.io.*;

public class Lab5TokenTest {

public static void main(String args[]) throws IOException {

 char L_br = '(';
 char R_br = ')';
 
  File it = new File("test.dat");
  LStack in = new LStack();

  if (it.exists()) {
   
    FileReader fr = new FileReader(it);
    BufferedReader br = new BufferedReader(fr);
    String s;
    // Build the Stack
    in.clear();
    System.out.println("List the input records");
    StackTokenTest t = new StackTokenTest();
    while ((s = br.readLine()) != null){        
     System.out.println(s);
     if(s.length()>0)
      in.push(s);
    }
    br.close();
   
     System.out.println("Print the stack");
     System.out.println(in.toString());
     while (in.length()>0)
     {
        System.out.println("Stack size is : "+in.length());
        s = in.pop();
        t.setUp();
        if (t.testToken(s))
          System.out.println(s+" is valid ");
        else
          System.out.println(s+" is invalid");
      }
     
    }
   else
    System.out.println("File named " + args[0] + " does not exist");
 }

}