Question

In C++:

This is the problem:

[(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 need number 3 completed.

This is the code:

#include <iostream>

#include <string.h>

#include <stack>

#include <queue>

#include <string>

#include <bits/stdc++.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);

}

// 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();

}

}

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;

}

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);

char exp[] = "231*+9-";

cout<<"\npostfix evaluation: "<< evaluatePostfix(exp);

cout<<"\n"<<endl;

return 0;

}

Answer 1

#include<iostream>
#include <sstream>
#include <string>
#include <cmath>

using namespace std;
class node{
public:
int data;
node* next;
};
node* head=NULL;
void insert(int val)
{
node* newnode=new node();
newnode->data=val;
newnode->next=NULL;
if(head==NULL)
{
head=newnode;
return;
}
node* temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newnode;
}

long long Addition()
{
long long additionResult = 0;
node* temp=head;
while(temp->next!=NULL)
{
additionResult += temp->data;
temp=temp->next;
}
additionResult += temp->data;
return additionResult;
}

long long Subtraction()
{
  
node* temp=head;
long long subtractionResult = temp->data;
temp=temp->next;
while(temp->next!=NULL)
{
subtractionResult -= temp->data;
temp=temp->next;
}
subtractionResult -= temp->data;
return subtractionResult;
}
long long Multiplication()
{
long long multiplicationResult = 1;
node* temp=head;
while(temp->next!=NULL)
{
multiplicationResult *= temp->data;
temp=temp->next;
}
multiplicationResult *= temp->data;
return multiplicationResult;
}

long long Exponent()
{
  
node* temp=head;
long long exponentResult = temp->data;
temp=temp->next;
while(temp->next!=NULL)
{
cout<<endl<<exponentResult<<" "<<temp->data<<endl;
exponentResult += pow(exponentResult, temp->data);
cout<<exponentResult<<" ";
temp=temp->next;
}
exponentResult += pow(exponentResult, temp->data);
return exponentResult;
}

void display()
{
node* temp=head;
while(temp->next!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<temp->data<<"\n";
}
int main()
{
int inputInteger = 1234;
  
ostringstream str1; // for converting integer to string
str1 << inputInteger;
string inputString = str1.str();
  
for( int itr = 0; itr < inputString.length(); insert(inputString[itr]-48), itr++); // insert each digit of the input integer to list

int choice;
cout<<"Enter choice : \n 1: Addition\n 2:Subtraction\n 3: Multiplication\n 4: Exponent\n";
cin>>choice;
switch (choice)
{
case 1:
cout<<"Addition of list is "<<Addition()<<endl;
break;
case 2:
cout<<"Subtraction of list is "<<Subtraction()<<endl;
break;
case 3:
cout<<"Multiplication of list is "<<Multiplication()<<endl;
break;
case 4:
cout<<"Exponent of list is "<<Exponent()<<endl;
break;
}
  
}

//Asymptotic running time of this code will be O(n)

// Kindly give me a thumbs up