Question

Java Please

[(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.

Answer 1

Here is your solution to the above problem:

1)

#include <iostream>
#include <stack>
#include <queue>
#include <string>
using namespace std;

void convertTosmall(string& str)
{
int length = str.length();
for (int i = 0; i < length; i++) {
int c = str[i];
if (isupper(c))
str[i] = tolower(c);   
}
return;
}

string removeSpaces(string& word) {
string newWord;
for (int i = 0; i < word.length(); i++) {
if (word[i] != ' ') {
newWord += word[i];
}
}

return newWord;
}

int main()
{
while ( true )
{
std::string letters;
std::cout << "Please enter a string (Enter - exit): ";
std::getline( std::cin, letters );
  
convertTosmall(letters);
letters = removeSpaces(letters);

if ( letters.empty() ) break;

std::stack<char>
s( std::stack<char>::container_type( letters.begin(), letters.end() ) );
std::queue<char>
q( std::queue<char>::container_type( letters.begin(), letters.end() ) );

while ( !s.empty() && s.top() == q.front() )
{
s.pop();
q.pop();
}

if ( s.empty() ) std::cout << "The string is a palindrome" << std::endl;
else std::cout << "The string is not a palindrome" << std::endl;
}

return 0;
}

// happy hack :)

2)

#include <bits/stdc++.h>
using namespace std;
  
// Utility function to print the queue
void Print(queue<int>& Q)
{
while (!Q.empty()) {
cout << Q.front() << " ";
Q.pop();
}
}
  
// Function to reverse the queue
void reverseQueue(queue<int>& Q)
{
stack<int> S;
while (!Q.empty()) {
S.push(Q.front());
Q.pop();
}
while (!S.empty()) {
Q.push(S.top());
S.pop();
}
}
  
int main()
{
queue<int> Q;
Q.push(10);
Q.push(20);
Q.push(30);
Q.push(40);
Q.push(50);
Q.push(60);
Q.push(70);
Q.push(80);
Q.push(90);
Q.push(100);
  
reverseQueue(Q);
Print(Q);
}

// happy hack :)

3)

//This program will add, substract and multiply two lists
//Lists are defined inside 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)

#include <iostream>
#include <string.h>
  
using namespace std;
  
// Stack type
struct Stack
{
int top;
unsigned capacity;
int* array;
};
  
// Stack Operations
struct Stack* createStack( unsigned capacity )
{
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
  
if (!stack) return NULL;
  
stack->top = -1;
stack->capacity = capacity;
stack->array = (int*) malloc(stack->capacity * sizeof(int));
  
if (!stack->array) return NULL;
  
return stack;
}
  
int isEmpty(struct Stack* stack)
{
return stack->top == -1 ;
}
  
char peek(struct Stack* stack)
{
return stack->array[stack->top];
}
  
char pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--] ;
return '$';
}
  
void push(struct Stack* stack, char op)
{
stack->array[++stack->top] = op;
}
  
  
// The main function that returns value of a given postfix expression
int evaluatePostfix(char* exp)
{
// Create a stack of capacity equal to expression size
struct Stack* stack = createStack(strlen(exp));
int i;
  
// See if stack was created successfully
if (!stack) return -1;
  
// Scan all characters one by one
for (i = 0; exp[i]; ++i)
{
// If the scanned character is an operand (number here),
// push it to the stack.
if (isdigit(exp[i]))
push(stack, exp[i] - '0');
  
// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[i])
{
case '+': push(stack, val2 + val1); break;
case '-': push(stack, val2 - val1); break;
case '*': push(stack, val2 * val1); break;
case '/': push(stack, val2/val1); break;
}
}
}
return pop(stack);
}
  
int main()
{
char exp[] = "231*+9-";
cout<<"postfix evaluation: "<< evaluatePostfix(exp);
return 0;
}

// happy hack :)

**************************************************************Thank You*************************************************