CodesJava

Easy learning with example program codes

Java delimiter matching using stack


A stack is an ADT – Abstract Data Type or a linear data structure. It is a LIFO data structure because it allows all data operations at one end only i.e. elements can be added and removed from the stack only at the top. LIFO stands for Last-in-first-out. The element which is inserted last, is accessed first.

Stack operations

  • push(): Pushing an element on the stack.
  • pop(): Removing an element from the stack.
  • peek(): Get the top data element of the stack, without removing it.
  • isFull(): Check if stack is full.
  • isEmpty(): Check if stack is empty.

Stack states

Overflow state: A stack is in overflow state if it does not contain enough space to accept an entity to be pushed.
Underflow state: A stack is in underflow state if we want to operate stack with pop operation and the stack is empty.

Stacks efficiency

As we discussed, all operations are done at the top of the stack so no comparisons or moves of elements are necessary. Hence it is very fast.

Examples

package com.codesjava;
 
public class Test {
    private int stackSize;
    private char[] stackArray;
    private int top;
 
    /**
     * constructor to create stack with size
     * @param size
     */
    public Test(int size) {
        this.stackSize = size;
        this.stackArray = new char[stackSize];
        this.top = -1;
    }
 
    /**
     * Adds new entry to the top of the stack
     * @param entry
     * @throws Exception 
     */
    public void push(char entry) throws Exception {
    	this.stackArray[++top] = entry;
    }
 
    /**
     * Removes an entry from the top of the stack.
     * @return
     * @throws Exception 
     */
    public char pop() throws Exception {
        if(this.isStackEmpty()){
        	System.out.println("Stack underflow.");
        }
        return this.stackArray[top--];
    }
 
    /**
     * Returns top of the stack without removing it.
     * @return
     */
    public int peek() {
        return stackArray[top];
    }
 
    /**
     * Returns true if the stack is empty
     * @return
     */
    public boolean isStackEmpty() {
        return (top == -1);
    }
 
    /**
     * Returns true if the stack is full
     * @return
     */
    public boolean isStackFull() {
        return (top == stackSize - 1);
    }
 
    public boolean isDelimiterMatching(String inputExpr) throws Exception {        
        for (int j = 0; j < inputExpr.length(); j++) {
            char ch = inputExpr.charAt(j);
            switch (ch) {
            case '{':
            case '[':
            case '(':
                    push(ch);
                    break;
            case '}':
            case ']':
            case ')':
                    if (!isStackEmpty()) {
                        char stackContent = pop();
                        if ((ch == '}' && stackContent != '{') 
                                || (ch == ']' && stackContent != '[')
                                || (ch == ')' && stackContent != '(')){
                            System.out.println("Mismatch found: " + ch + " at " + j);
                            return false;
                        }
                    } else {
                        System.out.println("Mismatch found: " + ch + " at " + j);
                        return false;
                    }
                    break;
            default: break;
            }
        }
        if (!isStackEmpty()){
            System.out.println("Error: missing right delimiter");
            return false;
        }
        return true;
    }
 
    public String reverseWord(String word) throws Exception{        
        StringBuilder sb = new StringBuilder();
        int size = word.length();
        for(int i=0;i<size;i++){
            push(word.charAt(i));
        }
        while(!isStackEmpty()){
            sb.append(pop());
        }
        return sb.toString();
    }
 
	public static void main(String args[]){
		try {
			String expression = "{(a+b)*(c+d)}";
			Test test = new Test(expression.length());
			System.out.println("Right expression: " + test.isDelimiterMatching(expression));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Output

Right expression: true
Sign Up/ Sign In
Ask a Question


Industrial Training

We offers Placement Oriented Training on Java, Spring, JSF, Hibernate, PHP, AngularJS, Angular 4, PLSQL, Oracle BI Publisher etc. We also provides Online training, please mail us at hr@codesjava.com.

Development

We also provides the Development services for Website Development , Java Development, PHP Development, Android App Development etc. You can contact us on hr@codesjava.com.

Copyright © 2018 CodesJava DMCA.com Protection Status SiteMap Reference: Java Wiki