This assignment is comprised of two unrelated programs. The first program is an

ID: 3707323 • Letter: T

Question

This assignment is comprised of two unrelated programs. The first program is an exercise in utilizing stacks, and the second program will be able utilizing queues. Stacks and postfix notation (or Reverse Polish Notation) In class, we have discussed how to perform postorder tree traversal, as well as briefly looked at evaluating expression trees. Postfix notation is a related method of representing mathematical expressions. Postfix notation is also called Reverse Polish Notation (RPN). Review this resource as well as the Lecture Notes on Queues and Stacks (last portion of the notes) for an in depth overview of RPN and strategies for completing this program. Priority Queue In computer science, a priority queue is an ADT which is similar to a regular queue; however, each entry in the queue is also has a “priority” associated with it. If two elements have the same priority, they are served according to their order in the queue. PriorityQueue *pq = new PriorityQueue(); pq->enqueue(“a”, 30); pq->enqueue(“b”, 10); pq->enqueue(“c”, 20); pq->enqueue(“d”, 10); cout << pq->dequeue() << pq->dequeue() << pq->dequeue() << pq->dequeue(); The string “acbd” is outputted is the “a” has the highest priority, followed by “c”, followed by “b”, and then followed by “d”. Program 1. (50 points) Reverse Polish Notation Calculator Write a program (rpn.cpp) that does the following: - Leverages the provided Stack class (in stack.h) accomplish the other goals of the assignment - Accepts a valid infix expression, converts it into RPN, and then evaluates the expression - If an invalid infix expression is provided, write an appropriate message to standard out and end the program - Print the convert postfix expression before evaluation, as well as its evaluated result - The major pieces of the program are broken into reusable functions - Infix expressions will contain the following operators: ( ) * / + - - When reading an infix expression, be sure to consider order of operators when converting to postfix - You may add new functions to the List and Stack classes in stack.h. if you feel they are necessary, but do not modify any existing functions - If you are having issues parsing input, you can create arrays with predetermined input to test the conversion process

Explanation / Answer

// File Name: Infix_PostFix_Evaluate.cpp
#include<iostream>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
using namespace std;

// Creates a structure for stack
struct MyStack
{
// For top counter
int top;
// To store capacity
unsigned size;
// To store data
int* data;
};// End of structure

// Function to creates a stack and returns it
struct MyStack* createStack(unsigned size)
{
// Dynamically allocates memory to a myStack
struct MyStack* myStack = (struct MyStack*) malloc(sizeof(struct MyStack));

// Checks if memory is not allocated then return NULL
if (!myStack)
return NULL;
// Otherwise assigns -1 to top counter
myStack -> top = -1;
// Assigns the size of the stack
myStack -> size = size;
// Dynamically allocates memory to pointer data
myStack -> data= (int*) malloc(myStack->size * sizeof(int));

// Checks if memory is not allocated to data then return NULL
if (!myStack -> data)
return NULL;
// Returns the stack created
return myStack;
}// End of function

// Function to return true if stack is empty otherwise returns false
int isEmpty(struct MyStack* myStack)
{
// If stack top counter value is -1 return true
return myStack -> top == -1 ;
}// End of function

// Function to return stack top element
char peek(struct MyStack* myStack)
{
return myStack -> data[myStack -> top];
}// End of function

// Function to delete stack top element and return it
char pop(struct MyStack* myStack)
{
// Calls the function to check whether the stack is empty or not
if (!isEmpty(myStack))
// If not empty returns the stack top position data and decrease the top value by one
return myStack -> data[myStack -> top--] ;
return '$';
}// End of function

// Function to push an operator in to the stack
void push(struct MyStack* myStack, char operatorCharacter)
{
myStack -> data[++myStack -> top] = operatorCharacter;
}// End of function

// Function to return precedence of operators
int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}// End of function

// Function to return converted infix expression to postfix expression
char * infixToPostfix(char* infixExp)
{
// Calls the function to create a stack
struct MyStack* myStack = createStack(strlen(infixExp));

// Pos counter for postfix expression
int pos = 0;
// See if stack was created successfully
if (!myStack)
return NULL;

// Push a 'N' character to the stack for beginning of expression
push(myStack, ('N' - '0'));
// Stores the length
int length = strlen(infixExp);
// Creates new pointer for postfix expression
char *postfixExp = new char[strlen(infixExp)];

// Loops till the length of the infix expression
for(int i = 0; i < length; i++)
{
// Checks if the scanned character is an operand, range from zero to nine
if((infixExp[i] - '0') >= 0 && (infixExp[i] - '0') <= 9)
// Adds it to postfix expression
postfixExp[pos++] = infixExp[i];

// Checks if the scanned character is an ‘(‘, push it to the stack.
else if(infixExp[i] == '(')
push(myStack, '(');

// If the scanned character is an ‘)’, pop and to output string from the stack until an ‘(‘ is encountered.
else if(infixExp[i] == ')')
{
// Loops till initial pushed character 'N' and till the peeked character from the stack is not '('
while(peek(myStack) != ('N' - '0') && peek(myStack) != '(')
{
// Extracts the character from the stack top position
char c = peek(myStack);
// Pops the top data from the stack
pop(myStack);
// Stores the peeked character in postfix expression
postfixExp[pos++] = c;
}// End of while loop

// Checks if the peeked character is '('
if(peek(myStack) == '(')
{
// Stores the peeked character
char c = peek(myStack);
// Pop the top element from the stack top position
pop(myStack);
}// End of if condition
}// End of else if condition

// Otherwise operator is scanned
else
{
// Loops till not initial character pushed 'N' and infix current operator is less than or equals to stack top characters
while(peek(myStack) != ('N' - '0') && prec(infixExp[i]) <= prec(peek(myStack)))
{
// Extracts the stack top character
char c = peek(myStack);
// Pops the stack top operator
pop(myStack);
// Adds the operator to the postfix expression
postfixExp[pos++] = c;
}// End of while loop
// Push the infix current operator to the stack top position
push(myStack, infixExp[i]);
}// End of else
}// End of for loop

// Pop all the remaining elements from the stack till the first character inserted 'N'
while(peek(myStack) != ('N' - '0'))
{
// Extracts the stack top character
char c = peek(myStack);
// Pops the stack top element
pop(myStack);
// Adds the element to the postfix expression
postfixExp[pos++] = c;
}// End of while loop
// Returns the postfix expression
return postfixExp;
}// End of function

// Function that returns value of a given postfix expression
int evaluatePostfix(char* exp)
{
// Create a stack of capacity equal to expression size
struct MyStack* myStack = createStack(strlen(exp));
int c;

// Checks if stack was created successfully
if (!myStack)
return -1;

// Scan all characters one by one
for (c = 0; exp[c]; ++c)
{
// Checks if the scanned character is an operand (number here), push it to the stack.
if (isdigit(exp[c]))
// - '0' to convert to integer
push(myStack, exp[c] - '0');

// Otherwise scanned character is an operator, pop two elements from stack apply the operator
else
{
// Extracts the operand values
int val1 = pop(myStack);
int val2 = pop(myStack);

// Checks the operator add evaluates according to the operator
switch (exp[c])
{
case '+':
push(myStack, val2 + val1);
break;
case '-':
push(myStack, val2 - val1);
break;
case '*':
push(myStack, val2 * val1);
break;
case '/':
push(myStack, val2/val1);
break;
}// End of switch - case
}// End of else
}// End of for loop
// Returns the stack top position data which is the result of the postfix expression evaluation result
return pop(myStack);
}// End of function

// main function definition
int main()
{
// To store index expression
char infixExp[100];
// Accepts infix expression
cout<<" Enter a infix expression: ";
cin>>infixExp;
// Calls the function to convert infix expression to postfix expression
char *postFix = infixToPostfix(infixExp);

// Displays the converted postfix expression
cout<<" The equivalent postfix expression of "<<infixExp<<" is: "<<postFix;

// Calls the function to evaluate postfix expression and displays the result
cout<<" The result of "<<postFix<<" is: "<<evaluatePostfix(postFix);
return 0;
}// End of function

Sample Output 1:

Enter a infix expression: 3+4

The equivalent postfix expression of 3+4 is:
34+
The result of 34+ is: 7

Sample Output 2:

Enter a infix expression: 2*3+1

The equivalent postfix expression of 2*3+1 is:
23*1+
The result of 23*1+ is: 7

Navigate

This assignment is comprised of two unrelated programs. The first program is an

This assignment is creative. I think you will enjoy it. Assess your every day li

This assignment is comprised of two unrelated programs. The first program is an

Question

Explanation / Answer

Related Questions

Navigate