Create a c++ program that takes as input a string from user which can be sorted
ID: 3675867 • Letter: C
Question
Create a c++ program that takes as input a string from user which can be sorted into an array. Use two stacks to determine precedence. will take a calculation string using a set of numbers and the operands +, -, *, / and will determine the result. Use the algorithm demonstrated below to implement the solution, but do it using a singly linked list to emulate the stack ADT.
Two stacks:
opStk holds operators
valStk holds values
Use $ as special “end of input” token with lowest precedence
Algorithm doOp()
x valStk.pop();
y valStk.pop();
op opStk.pop();
valStk.push( y op x )
Algorithm repeatOps( refOp ):
while ( valStk.size() > 1
prec(refOp) prec(opStk.top())
doOp()
Algorithm EvalExp()
Input: a stream of tokens representing an arithmetic expression (with numbers)
Output: the value of the expression
while there’s another token z
if isNumber(z) then
valStk.push(z)
else
repeatOps(z);
opStk.push(z)
repeatOps($);
return valStk.top()
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
/* Linked list node creation */
struct node
{
int data;
struct node* next;
};
/* Function to create a new node with given data of elements */
struct node *newNode(int data)
{
struct node *new_node = (struct node *) malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}
/* Function to insert a node at the beginning of the Linked List */
void push(struct node** head_ref, int new_data)
{
/* allocate node memory */
struct node* new_node = newNode(new_data);
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Adds contents of two linked lists and return the head node of resultant list */
struct node* addTwoLists (struct node* first, struct node* second)
{
struct node* res = NULL; // res is head node of the resultant list element
struct node *temp, *prev = NULL;
int carry = 0, sum;
while (first != NULL || second != NULL) //while both lists exist
{
// Calculate value of next digit in resultant list.
// The next digit is sum of following things
// (i) Carry
// (ii) Next digit of first list (if there is a next digit)
// (ii) Next digit of second list (if there is a next digit)
sum = carry + (first? first->data: 0) + (second? 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 = newNode(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) first = first->next;
if (second) second = second->next;
}
if (carry > 0)
temp->next = newNode(carry);
// return head of the resultant list
return res;
}
// A utility function to print a linked list
void printList(struct node *node)
{
while(node != NULL)
{
cout<<node->data;
node = node->next;
}
cout<<" ";
}
/* Driver program to test above function */
int main(void)
{
struct node* res = NULL;
struct node* first = NULL;
struct node* second = NULL;
// create first list 7->5->9->4->6
push(&first, 6);
push(&first, 4);
push(&first, 9);
push(&first, 5);
push(&first, 7);
printf("First List is ");
printList(first);
// create second list 8->4
push(&second, 4);
push(&second, 8);
printf("Second List is ");
printList(second);
// Add the two lists and see result
res = addTwoLists(first, second);
cout<<"Resultant list is ";
printList(res);
return 0;
}
output:
Input:
First List: 9->6->1 // represents number 169
Second List: 7->4->5 // represents number 457
Output
Resultant list: 6->2->6 // represents number 626
As same as the subtration,division and multiplication
or using polynomial function
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct poly
{
int coeff;
int exp;
struct poly *next;
}*head1=NULL,*head2=NULL,*head3=NULL,*head4=NULL,*temp,*ptr;
void create();
void makenode(int,int);
struct poly *insertend(struct poly *);
void display(struct poly *);
struct poly *addtwopoly(struct poly *,struct poly *,struct poly *);
struct poly *subtwopoly(struct poly *,struct poly *,struct poly *);
struct poly *multwopoly(struct poly *,struct poly *,struct poly *);
struct poly *dispose(struct poly *);
int search(struct poly *,int);
void main()
{
int ch,coefficient,exponent;
int listno;
while(1)
{
clrscr();
printf(“ntMenu”);
printf(“nt1. Create First Polynomial.”);
printf(“nt2. Display First Polynomial.”);
printf(“nt3. Create Second Polynomial.”);
printf(“nt4. Display Second Polynomial.”);
printf(“nt5. Add Two Polynomials.”);
printf(“nt6. Display Result of Addition.”);
printf(“nt7. Subtract Two Polynomials.”);
printf(“nt8. Display Result of Subtraction.”);
printf(“nt9. Multiply Two Polynomials.”);
printf(“nt10. Display Result of Product.”);
printf(“nt11. Dispose List.”);
printf(“nt12. Exit”);
printf(“nntEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nGenerating first polynomial:”);
printf(“nEnter coefficient?”);
scanf(“%d”,&coefficient);
printf(“nEnter exponent?”);
scanf(“%d”,&exponent);
makenode(coefficient,exponent);
head1 = insertend(head1);
break;
case 2:
display(head1);
break;
case 3:
printf(“nGenerating second polynomial:”);
printf(“nEnter coefficient?”);
scanf(“%d”,&coefficient);
printf(“nEnter exponent?”);
scanf(“%d”,&exponent);
makenode(coefficient,exponent);
head2 = insertend(head2);
break;
case 4:
display(head2);
break;
case 5:
printf(“nDisposing result list.”);
head3=dispose(head3);
head3=addtwopoly(head1,head2,head3);
printf(“Addition successfully done!”);
break;
case 6:
display(head3);
break;
case 7:
head3=dispose(head3);
head3=subtwopoly(head1,head2,head3);
printf(“Subtraction successfully done!”);
getch();
break;
case 8:
display(head3);
break;
case 9:
head3=dispose(head3);
head4=dispose(head4);
head4=multwopoly(head1,head2,head3);
break;
case 10:
display(head4);
break;
case 11:
printf(“Enter list number to dispose(1 to 4)?”);
scanf(“%d”,&listno);
if(listno==1)
head1=dispose(head1);
else if(listno==2)
head2=dispose(head2);
else if(listno==3)
head3=dispose(head3);
else if(listno==4)
head4=dispose(head4);
else
printf(“Invalid number specified.”);
break;
case 12:
exit(0);
default:
printf(“Invalid Choice!”);
break;
}
}
}
void create()
{
ptr=(struct poly *)malloc(sizeof(struct poly));
if(ptr==NULL)
{
printf(“Memory Allocation Error!”);
exit(1);
}
}
void makenode(int c,int e)
{
create();
ptr->coeff = c;
ptr->exp = e;
ptr->next = NULL;
}
struct poly *insertend(struct poly *head)
{
if(head==NULL)
head = ptr;
else
{
temp=head;
while(temp->next != NULL)
temp = temp->next;
temp->next = ptr;
}
return head;
}
void display(struct poly *head)
{
if(head==NULL)
printf(“List is empty!”);
else
{
temp=head;
while(temp!=NULL)
{
printf(“(%d,%d)->”,temp->coeff,temp->exp);
temp=temp->next;
}
printf(“bb “);
}
getch();
}
struct poly *addtwopoly(struct poly *h1,struct poly *h2,struct poly *h3)
{
/*
(5,3)->(6,1) + (7,3)->(9,2) = (12,3)->(6,1)->(9,2)
*/
struct poly *temp1,*temp2,*temp3;
temp1=h1;
temp2=h2;
while(temp1!=NULL || temp2!=NULL)
{
if(temp1->exp==temp2->exp)
{
makenode(temp1->coeff+temp2->coeff,temp1->exp);
h3=insertend(h3);
}
else
{
makenode(temp1->coeff,temp1->exp);
h3=insertend(h3);
makenode(temp2->coeff,temp2->exp);
h3=insertend(h3);
}
temp1=temp1->next;
temp2=temp2->next;
}
if(temp1==NULL && temp2!=NULL)
{
while(temp2!=NULL)
{
makenode(temp2->coeff,temp2->exp);
h3=insertend(h3);
temp2=temp2->next;
}
}
if(temp2==NULL && temp1!=NULL)
{
while(temp1!=NULL)
{
makenode(temp2->coeff,temp2->exp);
h3=insertend(h3);
temp1=temp1->next;
}
}
return h3;
}
struct poly *subtwopoly(struct poly *h1,struct poly *h2,struct poly *h3)
{
/*
(5,3)->(6,1) – (7,3)->(9,2) = (-2,3)+(6,1)-(9,2)
*/
struct poly *temp1,*temp2,*temp3;
temp1=h1;
temp2=h2;
while(temp1!=NULL || temp2!=NULL)
{
if(temp1->exp==temp2->exp)
{
makenode(temp1->coeff-temp2->coeff,temp1->exp);
h3=insertend(h3);
}
else
{
makenode(temp1->coeff,temp1->exp);
h3=insertend(h3);
makenode(-temp2->coeff,temp2->exp);
h3=insertend(h3);
}
temp1=temp1->next;
temp2=temp2->next;
}
if(temp1==NULL && temp2!=NULL)
{
while(temp2!=NULL)
{
makenode(temp2->coeff,temp2->exp);
h3=insertend(h3);
temp2=temp2->next;
}
}
if(temp2==NULL && temp1!=NULL)
{
while(temp1!=NULL)
{
makenode(-temp2->coeff,temp2->exp);
h3=insertend(h3);
temp1=temp1->next;
}
}
return h3;
}
struct poly *multwopoly(struct poly *h1,struct poly *h2,struct poly *h3)
{
/*
h1=(5,3)->(6,1) * h2=(7,3)->(9,2)
(5,3)->(7,3),(9,2) = (35,6),(45,5)
(6,1)->(7,3),(9,2) = (42,4),(54,3)
h3->(35,6)->(45,5)->(42,4)->(54,3)
(35,6)+(45,5)+(42,4)+(54,3)=Result
*/
int res=0;
struct poly *temp1,*temp2,*temp3;
printf(“nDisplaying First Polynomial:ntt”);
display(h1);
printf(“nDisplaying Second Polynomial:ntt”);
display(h2);
temp1=h1;
while(temp1!=NULL)
{
temp2=h2;
while(temp2!=NULL)
{
makenode(temp1->coeff*temp2->coeff,temp1->exp+temp2->exp);
h3=insertend(h3);
temp2=temp2->next;
}
temp1=temp1->next;
}
printf(“nDisplaying Initial Result of Product:ntt”);
display(h3);
getch();
temp1=h3;
while(temp1!=NULL)
{temp2=temp1->next;
res=0;
while(temp2!=NULL)
{
if(temp1->exp==temp2->exp)
res += temp2->coeff;
temp2=temp2->next;
}
if(search(head4,temp1->exp)==1)
{
makenode(res+temp1->coeff,temp1->exp);
head4=insertend(head4);
}
temp1=temp1->next;
}
return head4;
}
int search(struct poly *h,int val)
{
struct poly *tmp;
tmp=h;
while(tmp!=NULL)
{if(tmp->exp==val)
return 0;
tmp=tmp->next;
}
return 1;
}
struct poly *dispose(struct poly *list)
{
if(list==NULL)
{
printf(“List is already empty.”);
return list;
}
else
{
temp=list;
while(list!=NULL)
{
free(temp);
list=list->next;
temp=list;
}
return list;
}
}