Question

In: Computer Science

write a program using Java language that is- Implement Stack with a linked list, and demonstrate...

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.

Solutions

Expert Solution

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

Related Solutions

IN JAVA LANGUAGE Linked List-Based Stack Implementation Implement Stack using a Linked List Use the language...
IN JAVA LANGUAGE Linked List-Based Stack Implementation Implement Stack using a Linked List Use the language library LinkedList Stack methods will call the LinkedList methods You can use string as the object Instead of using an array, as the StackLab did, here you will use a Linked List from your language's library. Implement all the methods of Stack : push(), pop(), size(), printStackDown(), etc, using calls to the linked list methods that correspond to the actions need. In the array...
IN JAVA LANGUAGE Linked List-Based Queue Implementation Implement Queue using a Linked List. Use the language...
IN JAVA LANGUAGE Linked List-Based Queue Implementation Implement Queue using a Linked List. Use the language library LinkedList Queue methods will call the LinkedList methods You can use string as the object Instead of using an array, as the QueueLab did, here you will use a Linked List from your language's library. Implement all the methods of Stack : enqueue(), dequeue(), size(), printQueue(), etc, using calls to the linked list methods that correspond to the actions need. In the array...
write a java program to Implement a Priority Queue using a linked list. Include a main...
write a java program to Implement a Priority Queue using a linked list. Include a main method demonstrating enqueuing and dequeuing several numbers, printing the list contents for each.
JAVA Write a class for a Stack of characters using a linked list implementation. Write a...
JAVA Write a class for a Stack of characters using a linked list implementation. Write a class for a Queue of characters using a linked list implementation. Write a class for a Queue of integers using a circular array implementation.
Data structure program Implement (your own) the Radix Sort using single linked list java language
Data structure program Implement (your own) the Radix Sort using single linked list java language
Write a Java program to implement a Single Linked List that will take inputs from a...
Write a Java program to implement a Single Linked List that will take inputs from a user as Student Names. First, add Brian and Larry to the newly created linked list and print the output Add "Kathy" to index 1 of the linked list and print output Now add "Chris" to the start of the list and "Briana" to the end of the list using built-in Java functions. Print the output of the linked list.
Write a Java program to implement a double-linked list with addition of new nodes at the...
Write a Java program to implement a double-linked list with addition of new nodes at the end of the list. Add hard coded nodes 10, 20, 30, 40 and 50 in the program. Print the nodes of the doubly linked list.
Write a code to implement a python stack class using linked list. use these operations isEmpty...
Write a code to implement a python stack class using linked list. use these operations isEmpty   • push. • pop.   • peek. • size Time and compare the performances ( this is optional but I would appreciate it)
The program (​ stack-ptr.c​ ) implements stack using a linked list, however, it contains a race...
The program (​ stack-ptr.c​ ) implements stack using a linked list, however, it contains a race condition and is not appropriate for a concurrent environment. Using Pthreads mutex locks, fix the race condition. For reference, see Section 7.3.1 of SGG book.(Section 7.3.1 is about mutex and semaphores it does explain how to implement I'm just having a hard time finding the race condition within the code) /* * Stack containing race conditions */ #include #include #include typedef int value_t; //...
Write an efficient java program to implement an integer doubly linked list Dequeue which insertion and...
Write an efficient java program to implement an integer doubly linked list Dequeue which insertion and deletion can be than at either end. You have to write 6 methods: add front, delete front, add rear, delete rear, print forward (left to right) and print backward (right to left). After each addition or deletion dequeue elements are printed forward or backward respectively. Your main method should be as follow: public static void main(String args[]) { xxxxx dq = new xxxxx ();...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT