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();
}
}
}
}
Towers of Hanoi implementation using stack
package com.java2novice.ds.stack;
public class TowersOfHanoiImpl
{
private static MyDynamicStack[] tower;
public static void towersOfHanoi(int n)
{
tower
= new MyDynamicStack[4];
for
(int i = 0; i <= 3; i++)
{
tower[i]
= new MyDynamicStack(4);
}
for
(int d = n; d > 0; d--){
tower[1].push(new
Integer(d));
}
showTowerStates(n,
1, 2, 3);
}
public static void showTowerStates(int n,
int x, int y, int z)
{
if
(n > 0)
{
try
{
showTowerStates(n
- 1, x, z, y);
Integer
d = (Integer) tower[x].pop();
tower[y].push(d);
System.out.println("Move
disk " + d
+
" from tower "+ x + " to top of tower " + y);
showTowerStates(n
- 1, z, y, x);
}
catch(Exception ex){}
}
}
public static void
main(String[] args)
{
System.out.println("Running 3 disk problem:");
towersOfHanoi(3);
}
}
public 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();
}
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--];
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