Question

Please hurry, will upvote if correct!

This is the problem in Java:

[(1)] A palindrome is a string that reads the same forwards as backwards. Using only a fixed number of stacks and queues, the stack and queue ADT functions, and a fixed number of int and char variables, write an algorithm to determine if a string is a palindrome. Assume that the string is read from standard input one character at a time. The algorithm should output true or false as appropriate

[(2)] Let Q be a non-empty queue, and let S be an empty stack. Using only the stack and queue ADT functions and a single element variable X, write an algorithm to reverse the order of the elements in Q.

[(3)] Use singly linked lists to implement integers of unlimited size. Each node of the list should store one digit of the integer. You should implement addition, subtraction, multiplication, and exponentiation operations. Limit exponents to be positive integers. What is the asymptotic running time for each of your operations, expressed in terms of the number of digits for the two operands of each function?

[(4)] Implement a program that can input an expression in postfix notation and output its value.

I have working code (below), but please check that the above conditions are met and implement parts 2 and 3 as necessary, keeping number 4 in mind.

import java.io.*;
import java.util.Stack;
import java.util.LinkedList; //libraries required
import java.util.Queue;
import java.util.Scanner;

public class Palindrome{

   public static boolean check_Palindrome(String str){ //method to check if the given string is palindrome or not

       Queue queue = new LinkedList(); //declaring the queue

       Stack stack = new Stack(); //declaring the stack

       Character alphabet;

       int count = 0;
  
   for (int i = 0; i < str.length(); i++){
             
           alphabet = str.charAt(i);   

           queue.add(alphabet); //add each character to the queue and the stack

           stack.push(alphabet);
          
   }
      
       while (!queue.isEmpty()){
             
           if (queue.remove()!=stack.pop()) //removal of each character from queue and stack must be same to say it's palindrome
               count++;
      
       }

       if(count==0) //if the count equal to zero then it is a palindrome
           return true;
       else
           return false;
   }

   public static void main(String[] args) {

       String str;

       Scanner sc = new Scanner(System.in);

       System.out.print("Enter the string : "); //taking string from user

       str = sc.nextLine();

      
       if(check_Palindrome(str))
           System.out.println("True");
      
       else
           System.out.println("False");

      
   }

}

Answer 1

1) The algorithm for checking if a string is a palindrome using stack data structure functions are:

· Find the length of the string say len. Now, find the mid as mid = len / 2.

· Push all the elements till mid into the stack i.e. str[0…mid-1].

· If the length of the string is odd then neglect the middle character.

· Till the end of the string, keep popping elements from the stack, and compare it with the current character i.e. string[i].

· If there is a mismatch then the string is not a palindrome. If all the elements match then the string is a palindrome.

2) For reversing the queue one approach could be to store the elements of the queue in a temporary data structure in a manner such that if we re-insert the elements in the queue they would get inserted in reverse order. Since stack works on the LIFO paradigm, this can be done using a stack. This will be a two-step process:

• Pop the elements from the queue and insert them into the stack. (Topmost element of the stack is the last element of the queue)
• Pop the elements of the stack to insert back into the queue. (The last element is the first one to be inserted into the queue.

3) For the above problem we will simply use a self-made Singly linked list data structure implementation.

CODE:

//This program will add, subtract and multiply two lists

//Lists are defined inside the program

class LinkedList

{

    static Node head1, head2;

    static class Node {

        int data;

        Node next;

        Node(int d) {

            data = d;

            next = null;

        }

    }

    /* Adds contents of two linked lists and return the head node of resultant list */

    Node addTwoLists(Node first, Node second) {

        Node res = null; // res is head node of the resultant list

        Node prev = null;

        Node temp = null;

      int carry = 0, sum;

        while (first != null || second != null) //while both lists exist

        {

            sum = carry + (first != null ? first.data : 0)

                    + (second != null ? second.data : 0);

            // update carry for next calulation

            carry = (sum >= 10) ? 1 : 0;

            // update sum if it is greater than 10

            sum = sum % 10;

            // Create a new node with sum as data

            temp = new Node(sum);

            // if this is the first node then set it as head of

            // the resultant list

            if (res == null) {

                res = temp;

            } else // If this is not the first node then connect it to the rest.

            {

                prev.next = temp;

            }

            // Set prev for next insertion

            prev = temp;

            // Move first and second pointers to next nodes

            if (first != null) {

                first = first.next;

            }

            if (second != null) {

                second = second.next;

            }

        }

        if (carry > 0) {

            temp.next = new Node(carry);

        }

        // return head of the resultant list

        return res;

    }

    //function to subtract given lists

    Node subtract(Node first, Node second, int borrow) {

        Node result = new Node(borrow);

        int value = borrow;

        //return null when both list are null

        if (first == null && second == null && borrow == 0)

            return null;

        if (first.data >= second.data) {

            value += first.data - second.data;

            borrow = 0;

        } else {

            if (first.next != null) {

                value += (first.data) + 10 - second.data;

                borrow = -1;

            } else {

                value += (first.data) + 10 - second.data;

                value = value * (-1);

                borrow = 0;

            }

        }

        result.data = value;

        //Recurse

        if (first.next != null || second.next != null || borrow < 0) {

            Node more = subtract(first.next != null ? first.next : null,

                    second.next != null ? second.next : null,

                    borrow < 0 ? -1 : 0);

            result.next = more;

        }

        return result;

    }

    //function to convert list into number

    static int getNumber(Node list) {

        int number = 0;

        while (list != null) {

            number = 10 * number + list.data;

            list = list.next;

        }

        return number;

    }

    //function to traverse a list

    static Node process(Node list) {

        Node head = list;

        int carry = 0, i = 0;

        while (head != null && head.next != null) {

            i = head.data;

            head.data = (carry + i) % 10;

            carry = (i + carry) / 10;

            head = head.next;

        }

        head.data = head.data + carry;

        return reverse(list);

    }

    //function to reverse the given list

    static Node reverse(Node list) {

        if (list == null)

            return null;

        Node current = list, previous = null, forward;

        while (current != null) {

            forward = current.next;

            current.next = previous;

            previous = current;

            current = forward;

        }

        return previous;

    }

    static Node multiply(Node first, Node second) {

        //When both lists are null, return null

        if (first == null || second == null)

            return null;

        int number = getNumber(first); //convert one list into number

        //traverse the second list and multiply the number with the current element of the list and store in the new list.

        Node current = second;

        Node result = null;

        while (current != null) {

            if (result == null) {

                result = new Node(current.data * number);

            } else {

                //multiply current element with the "number" and store in the new list node

                Node temp = new Node(current.data * number);

                temp.next = result;

                result = temp;

            }

            current = current.next;

        }

        return process(result);

    }

    /*function to print a linked list */

    void printList(Node head) {

        while (head != null) {

            System.out.print(head.data + " ");

            head = head.next;

        }

        System.out.println("");

    }

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        // creating first list

        list.head1 = new Node(7);

        list.head1.next = new Node(5);

        list.head1.next.next = new Node(9);

        list.head1.next.next.next = new Node(4);

        list.head1.next.next.next.next = new Node(6);

        System.out.print("First List is ");

        list.printList(head1);

        // creating seconnd list

        list.head2 = new Node(8);

        list.head2.next = new Node(4);

        list.head2.next.next = new Node(8);

        list.head2.next.next.next = new Node(4);

        list.head2.next.next.next.next = new Node(4);

        System.out.print("Second List is ");

        list.printList(head2);

        // add the two lists and see the result

        Node add = list.addTwoLists(head1, head2);

        System.out.print("\r\nResultant List after Addition is : ");

        list.printList(add);

        Node sub = list.subtract(head1, head2, 0);

        System.out.print("\r\nResultant List after Substraction is : ");

        list.printList(sub);

        Node multiply = list.multiply(head1, head2);

        System.out.print("\r\nResultant List after Multiplication is : ");

        list.printList(multiply);

    }

}

Output:

4)

CODE:

#include<bits/stdc++.h>

using namespace std;
float scanNum(char ch) {
int value;
value = ch;
return float(value-'0'); //return float from character
}
int isOperator(char ch) {
if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
return 1; //character is an operator
return -1; //not an operator
}
int isOperand(char ch) {
if(ch >= '0' && ch <= '9')
return 1; //character is an operand
return -1; //not an operand
}
float operation(int a, int b, char op) {
//Perform operation
if(op == '+')
return b+a;
else if(op == '-')
return b-a;
else if(op == '*')
return b*a;
else if(op == '/')
return b/a;
else if(op == '^')
return pow(b,a); //find b^a
else
return INT_MIN; //return negative infinity
}
float postfixEval(string postfix) {
int a, b;
stack<float> stk;
string::iterator it;
for(it=postfix.begin(); it!=postfix.end(); it++) {
//read elements and perform postfix evaluation
if(isOperator(*it) != -1) {
a = stk.top();
stk.pop();
b = stk.top();
stk.pop();
stk.push(operation(a, b, *it));
}else if(isOperand(*it) > 0) {
stk.push(scanNum(*it));
}
}
return stk.top();
}

int main() {
string postfix;
cout<<"Enter the postfix expression.\n";
cin>>postfix;
cout << "The result is: "<<postfixEval(postfix);
return 0;
}

Output: