Question

write a program using Java language that is-

1. Implement Stack with a linked list, and demonstrate that it can solve the Tower of Hanoi problem.

2. Write implementation body of method “infixToPrefix(String[] e)” of class ArithmeticExpression to convert infix expressions into prefix expressions.

Answer 1

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