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();
}
}
}
}
Evaluation of an infix expression that
is fully parenthesized using stack in java
package com.java2novice.ds.stack;
import java.util.StringTokenizer;
public class InfixFullParantEx
{
public static String
evaluateInfix(String exps)
{
exps
= exps.replaceAll("\\s+", "");
MyGenericsStack
stack = new MyGenericsStack(exps.length());
StringTokenizer
tokens = new StringTokenizer(exps, "{}()*/+-", true);
while(tokens.hasMoreTokens())
{
String
tkn = tokens.nextToken();
if(tkn.equals("(")
||
tkn.equals("{")
||
tkn.matches("[0-9]+")
||
tkn.equals("*")
||
tkn.equals("/")
||
tkn.equals("+")
||
tkn.equals("-"))
{
stack.push(tkn);
}
else if(tkn.equals("}") || tkn.equals(")"))
{
try
{
int
op2 = Integer.parseInt(stack.pop());
String
oprnd = stack.pop();
int
op1 = Integer.parseInt(stack.pop());
if(!stack.isStackEmpty())
{
stack.pop();
}
int
result = 0;
if(oprnd.equals("*"))
{
result
= op1*op2;
}
else if(oprnd.equals("/"))
{
result
= op1/op2;
}
else
if(oprnd.equals("+"))
{
result
= op1+op2;
}
else
if(oprnd.equals("-"))
{
result
= op1-op2;
}
stack.push(result+"");
}
catch (Exception e)
{
e.printStackTrace();
break;
}
}
}
String
finalResult = "";
try
{
finalResult
= stack.pop();
}
catch (Exception e)
{
e.printStackTrace();
}
return
finalResult;
}
public
static void main(String a[])
{
String
expr = "((2*5)+(6/2))";
System.out.println("Expression:
"+expr);
System.out.println("Final
Result: "+evaluateInfix(expr));
expr
= "(((2 * 5) - (1 * 2)) / (11 - 9))";
System.out.println("Expression:
"+expr);
System.out.println("Final
Result: "+evaluateInfix(expr));
}
}
public class MyGenericsStack
{
private int stackSize;
private T[] stackArr;
private int top;
public
MyGenericsStack(int size)
{
this.stackSize
= size;
this.stackArr
= (T[]) new Object[stackSize];
this.top
= -1;
}
public void push(T
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
T pop() throws Exception
{
if(this.isStackEmpty())
{
throw
new Exception("Stack is empty. Can not remove element.");
}
T
entry = this.stackArr[top--];
System.out.println("Removed
entry: "+entry);
return
entry;
}
public T peek()
{
return
stackArr[top];
}
private void
increaseStackCapacity()
{
T[]
newStack = (T[]) new Object[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);
}
}
No comments:
Post a Comment