In: Computer Science
write a program using Java language that is-
Implement Stack with a linked list, and demonstrate that it can solve the Tower of Hanoi problem.
Write implementation body of method “infixToPrefix(String[] e)” of class ArithmeticExpression to convert infix expressions into prefix expressions.
Tower of Hanoi is a mathematical puzzle where
we have three rods and n disks. The objective of the puzzle is to
move the entire stack to another rod, obeying the following simple
rules:
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the
stacks and placing it on top of another stack i.e. a disk can only
be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.
//This is the stack class using array
class Stack {
int size;
int top;
int stackArr[];
Stack createStack(int size) {
Stack stack = new Stack();
stack.size = size;
stack.top = -1;
stack.stackArr = new int[size];
return stack;
}
boolean isEmpty(Stack stack) {
return (stack.top == -1);
}
void push(Stack stack, int item) {
if(stack.top == stack.size - 1)
return;
stack.stackArr[++stack.top] = item;
}
int pop(Stack stack) {
if(isEmpty(stack))
return 0;
return stack.stackArr[stack.top--];
}
}
//This is the stack class using linked list
class Stack {
private Stack top;
private int data;
private Stack next;
public Stack createStack(int value) {
Stack stack = new Stack();
stack.data = value;
top = stack;
return stack;
}
public boolean isEmpty(Stack stack) {
return (stack.top == null);
}
public int push(Stack stack, int value) {
Stack newStack = new Stack();
stack = newStack;
stack.data = value;
stack.next = top;
top = stack;
return stack.data;
}
public int pop(Stack stack) {
int temp = 0;
if(isEmpty(stack)) {
System.out.println("Stack underflow");
System.exit(1);
}
else {
temp = top.data;
top = top.next;
}
return temp;
}
public void show(Stack stack) {
if(isEmpty(stack)) {
System.out.println("Stack underflow");
System.exit(1);
}
else {
Stack newStack = top;
if(newStack.next != null) {
System.out.print(newStack.data + " => ");
newStack = newStack.next;
}
System.out.print(newStack.data);
}
}
}
class TOH {
private Stack stk;
TOH() {
stk = new Stack();
}
void moveDisksBetweenTwoPoles(Stack src, Stack dest, char s, char d) {
int pole1TopDisk = stk.pop(src);
int pole2TopDisk = stk.pop(dest);
if (pole1TopDisk == 0) {
stk.push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
else if (pole2TopDisk == 0) {
stk.push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
else if (pole1TopDisk > pole2TopDisk) {
stk.push(src, pole1TopDisk);
stk.push(src, pole2TopDisk);
moveDisk(d, s, pole2TopDisk);
}
else {
stk.push(dest, pole2TopDisk);
stk.push(dest, pole1TopDisk);
moveDisk(s, d, pole1TopDisk);
}
}
void moveDisk(char fromPeg, char toPeg, int disk) {
System.out.println("Move disk " + disk +
" from "+ fromPeg + " to " + toPeg);
}
int totNumOfMoves(int num_of_disks) {
int numOfMoves = 0;
numOfMoves = (int)(Math.pow(2, num_of_disks) - 1);
return numOfMoves;
}
void loadfirstTower(Stack src, int num_of_disks) {
for(int i = num_of_disks; i >= 1; i--)
stk.push(src, i);
}
void tohIterative(int num_of_disks, Stack src, Stack aux, Stack dest) {
int i, total_num_of_moves;
char s = 'A', d = 'B', a = 'C';
loadfirstTower(src, num_of_disks);
if (num_of_disks % 2 == 0) {
char temp = d;
d = a;
a = temp;
}
for (i = 1; i <= totNumOfMoves(num_of_disks); i++) {
if (i % 3 == 1)
moveDisksBetweenTwoPoles(src, dest, s, d);
else if (i % 3 == 2)
moveDisksBetweenTwoPoles(src, aux, s, a);
else if (i % 3 == 0)
moveDisksBetweenTwoPoles(aux, dest, a, d);
}
}
}
public class Main {
public static void main(String[] args) {
int num_of_disks = 4;
TOH ob = new TOH();
Stack src = new Stack();
Stack dest = new Stack();
Stack aux = new Stack();
try {
ob.tohIterative(num_of_disks, src.createStack(num_of_disks), aux.createStack(num_of_disks), dest.createStack(num_of_disks));
}
catch (NegativeArraySizeException e){
System.out.println("The number of disk(s) cannot be negative");
}
}
}
INFIX TO PREFIX:
import java.util.Stack;
public class InfixToPreFix {
static int precedence(char c){
switch (c){
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
static StringBuilder infixToPreFix(String expression){
StringBuilder result = new StringBuilder();
StringBuilder input = new StringBuilder(expression);
input.reverse();
Stack<Character> stack = new Stack<Character>();
char [] charsExp = new String(input).toCharArray();
for (int i = 0; i < charsExp.length; i++) {
if (charsExp[i] == '(') {
charsExp[i] = ')';
i++;
}
else if (charsExp[i] == ')') {
charsExp[i] = '(';
i++;
}
}
for (int i = 0; i <charsExp.length ; i++) {
char c = charsExp[i];
//check if char is operator or operand
if(precedence(c)>0){
while(stack.isEmpty()==false && precedence(stack.peek())>=precedence(c)){
result.append(stack.pop());
}
stack.push(c);
}else if(c==')'){
char x = stack.pop();
while(x!='('){
result.append(x);
x = stack.pop();
}
}else if(c=='('){
stack.push(c);
}else{
//character is neither operator nor "("
result.append(c);
}
}
for (int i = 0; i <=stack.size() ; i++) {
result.append(stack.pop());
}
return result.reverse();
}
public static void main(String[] args) {
String exp = "A+B*(C^D-E)";
System.out.println("Infix Expression: " + exp);
System.out.println("Prefix Expression: " + infixToPreFix(exp));
}
}
Infix Expression: A+B*(C^D-E) Prefix Expression: +A*B-^CDE