Write a program to find out delimiter matching using stack
package com.java2novice.ds.stack;
public class MyDelimiterMatching
{
public static void main(String a[])
{
MyDelimiterMatching
mdm = new MyDelimiterMatching();
String
expression = "{(a+b)*(c+d)}";
boolean
result = mdm.isDelimiterMatching(expression);
System.out.println(expression
+" == "+result);
expression
= "{(a+b)+[x*(c+d)]}";
result
= mdm.isDelimiterMatching(expression);
System.out.println(expression
+" == "+result);
expression
= "{(a+b)+[x*(c+d)}}";
result
= mdm.isDelimiterMatching(expression);
System.out.println(expression
+" == "+result);
}
public boolean isDelimiterMatching(String
inputExpr)
{
int
stackSize = inputExpr.length();
StackImpl
theStack = new StackImpl(stackSize);
for
(int j = 0; j < inputExpr.length(); j++)
{
char
ch = inputExpr.charAt(j);
switch
(ch)
{
case
'{':
case
'[':
case
'(':
theStack.push(ch);
break;
case
'}':
case
']':
case
')':
if
(!theStack.isStackEmpty())
{
char
stackContent = theStack.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 (!theStack.isStackEmpty())
{
System.out.println("Error:
missing right delimiter");
return false;
}
return true;
}
}
class
StackImpl
{
private int stackSize;
private char[] stackArr;
private int top;
public StackImpl(int size)
{
this.stackSize
= size;
this.stackArr
= new char[stackSize];
this.top
= -1;
}
public void push(char entry)
{
this.stackArr[++top]
= entry;
}
public char pop()
{
char
entry = this.stackArr[top--];
return
entry;
}
public char peek()
{
return
stackArr[top];
}
public boolean isStackEmpty()
{
return
(top == -1);
}
public boolean isStackFull()
{
return
(top == stackSize - 1);
}
}
Convert a decimal into a binary number using stack
package com.java2novice.ds.stack;
public class MyDecimalToBinary
{
public static String
convertDecialToBinary(int number)
{
StringBuilder
binary = new StringBuilder();
MyDynamicStack
stack = new MyDynamicStack(10);
if(number
== 0)
{
binary.append("0");
}
else
{
while(number
!= 0)
{
stack.push(number%2);
number
= number/2;
}
}
while(!stack.isStackEmpty())
{
try
{
binary.append(stack.pop());
}
catch (Exception e)
{
e.printStackTrace();
}
}
return
binary.toString();
}
public static void
main(String a[])
{
System.out.println("Binary
value of 2 is: "+convertDecialToBinary(2));
System.out.println("Binary
value of 15 is: "+convertDecialToBinary(15));
System.out.println("Binary
value of 23 is: "+convertDecialToBinary(23));
}
}
class MyDynamicStack
{
private int stackSize;
private int[] stackArr;
private int top;
public MyDynamicStack(int size)
{
this.stackSize
= size;
this.stackArr
= new int[stackSize];
this.top
= -1;
}
public void push(int entry)
{
if(this.isStackFull())
{
System.out.println(("Stack is
full. Increasing the capacity."));
this.increaseStackCapacity();
}
System.out.println("Adding:
"+entry);
this.stackArr[++top] = entry;
}
public int pop() throws Exception
{
if(this.isStackEmpty())
{
throw new Exception("Stack is empty. Can
not remove element.");
}
int entry = this.stackArr[top--];
System.out.println("Removed
entry: "+entry);
return entry;
}
public long peek()
{
return
stackArr[top];
}
private void increaseStackCapacity()
{
int[]
newStack = new int[this.stackSize*2];
for(int
i=0;i
{
newStack[i]
= this.stackArr[i];
}
this.stackArr
= newStack;
this.stackSize
= this.stackSize*2;
}
public boolean isStackEmpty()
{
return
(top == -1);
}
public
boolean isStackFull()
{
return (top == stackSize - 1);
}
public static void main(String[] args)
{
MyDynamicStack stack = new
MyDynamicStack(2);
for(int i=1;i<10 i="" span="">
{
stack.push(i);
}
for(int i=1;i<4 i="" span="">
{
try
{
stack.pop();
}
catch (Exception e)
{
e.printStackTrace();
}
}
}
}
No comments:
Post a Comment