This assignment is comprised of two unrelated programs. The first program is an
ID: 3707046 • 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
stack.h
class ListNode
{
private:
int data;
ListNode* prev;
ListNode* next;
public:
ListNode() { prev = next = NULL; }
ListNode(int d, ListNode* p, ListNode* n) { data = d; prev = p; next
= n; }
friend class List;
};
class List
{
private:
ListNode* list_head;
ListNode* list_tail;
public:
List() { list_head = list_tail = NULL; }
~List() { clear(); }
bool isEmpty() { return list_head == NULL; }
bool contains(int value);
void addToHead(int value);
void addToTail(int value);
int head() { return list_head->data; }
int tail() { return list_tail->data; }
int removeHead();
int removeTail();
void clear();
};
bool List::contains(int value)
{
ListNode *temp = list_head;
while (temp != NULL && temp->data != value)
temp = temp->next;
return temp != NULL;
}
void List::addToHead(int value)
{
if (isEmpty())
{
list_head = list_tail = new ListNode(value, NULL, NULL);
}
else
{
list_head = new ListNode(value, NULL, list_head);
list_head->next->prev = list_head;
}
}
void List::addToTail(int value)
{
if (isEmpty())
{
list_head = list_tail = new ListNode(value, NULL, NULL);
}
else
{
list_tail = new ListNode(value, list_tail, NULL);
list_tail->prev->next = list_tail;
}
}
int List::removeHead()
{
int value = list_head->data;
if (list_head == list_tail)
{
delete list_tail;
list_head = list_tail = NULL;
}
else
{
list_head = list_head->next;
delete list_head->prev;
list_head->prev = NULL;
}
return value;
}
int List::removeTail()
{
int value = list_head->data;
if (list_head == list_tail)
{
delete list_tail;
list_head = list_tail = NULL;
}
else
{
list_tail = list_tail->prev;
delete list_tail->next;
list_tail->next = NULL;
}
return value;
}
void List::clear()
{
while (!isEmpty())
removeTail();
}
class Stack
{
private:
List* list;
public:
Stack() { list = new List(); }
~Stack() { delete list; }
bool isEmpty() { return list->isEmpty(); }
void clear() { list->clear(); }
void push(int data) { list->addToHead(data); }
int pop() { return list->removeHead(); }
int top() { return list->head(); }
};
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. PriorityQueueenqueue ("a", 30); pq->enqueue("b", 10); pq-enqueue ("c, 20); pq->enqueue ("d", 10); coutExplanation / Answer
Solution for problem 1:
#include <iostream>
#include <string>
#include "stack.h"
using namespace std;
string infixToPostFix(string infix);
int higherPrecedenceValidate(char op1, char op2);
int getPrecedence(char op);
int evaluatePostFix(string postfix);
int main()
{
string infix,postfix;
int result;
cout << "Infix: ";
cin >> infix;
postfix = infixToPostFix(infix);
cout << " Postfix: " << postfix << endl << endl;
if(postfix != "Wrong Expression"){
result = evaluatePostFix(postfix);
cout << "Result: " << result << endl << endl;
}
}
string infixToPostFix(string infix){
Stack<char> operators;
bool isMathOperatorRepeated = false;
bool isOperaendRepeated = false;
string postfix;
for(int i = 0; i < infix.size(); i++){
// Checking Operator
if(infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/'){
if(isMathOperatorRepeated){
postfix = "Wrong Expression";
/*
After this for loop there is while loop
which is checking rest of the char and add it with postfix string .
So this pushed char should be pop out
beacuse infix expression is wrong.
*/
while (!operators.IsEmpty())
{
operators.Pop();
}
break;
}
while (!operators.IsEmpty() && higherPrecedenceValidate(operators.Top(),infix[i]))
{
postfix = postfix + operators.Top();
operators.Pop();
}
operators.Push(infix[i]);
isMathOperatorRepeated = true;
isOperaendRepeated = false;
}
// Checking Operand
else if(infix[i] >= '0' && infix[i] <= '9')
{
if(isOperaendRepeated){
postfix = "Wrong Expression";
/*
After this for loop there is while loop
which is checking rest of the char and add it with postfix string .
So this pushed char should be pop out
beacuse infix expression is wrong.
*/
while (!operators.IsEmpty())
{
operators.Pop();
}
break;
}
postfix = postfix + infix[i];
isMathOperatorRepeated = false;
isOperaendRepeated = true;
}
//Checking open bracket
else if(infix[i] == '(' ){
operators.Push(infix[i]);
isMathOperatorRepeated = false;
isOperaendRepeated = false;
}
//Checking closing bracket
else if(infix[i] == ')' ){
while (!operators.IsEmpty() && operators.Top() != '(')
{
postfix = postfix + operators.Top();
operators.Pop();
}
/*
checking stack beacuse we know
that if the infix char is ')'
and the stack is empty then the infix expression is wrong
*/
if(operators.IsEmpty()){
postfix = "Wrong Expression";
break;
}
else{
operators.Pop();
}
// poping the opening bracket
isMathOperatorRepeated = false;
isOperaendRepeated = false;
}
// checking that infix expression has invalid char
else{
postfix = "Wrong Expression";
/*
After this for loop there is while loop
which is checking rest of the char in stack.
So this pushed char should be pop out
beacuse infix expression is wrong.
*/
while (!operators.IsEmpty())
{
operators.Pop();
}
break;
}
}
// poping rest of element from the stack..
while (!operators.IsEmpty())
{
if(operators.Top() == '('){
postfix = "Wrong Expression";
break;
}
else{
postfix = postfix + operators.Top();
operators.Pop();
}
}
return postfix;
}
int evaluatePostFix(string postfix){
Stack<int> finalNumbers;
for(int i = 0; i < postfix.size(); i++){
// Checking Operator
if(postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/'){
int resultOfTwoNumber;
int number2 = finalNumbers.Top();
finalNumbers.Pop();
int number1 = finalNumbers.Top();
finalNumbers.Pop();
switch (postfix[i])
{
case '+':
resultOfTwoNumber = number1 + number2;
break;
case '-':
resultOfTwoNumber = number1 - number2;
break;
case '*':
resultOfTwoNumber = number1 * number2;
break;
case '/':
resultOfTwoNumber = number1 / number2;
break;
}
finalNumbers.Push(resultOfTwoNumber);
}
// Checking Operand
else if(postfix[i] >= '0' && postfix[i] <= '9')
{
finalNumbers.Push(postfix[i] - '0');
}
}
return finalNumbers.Top();
}
int higherPrecedenceValidate(char operator1, char operator2)
{
int op1 = getPrecedence(operator1);
int op2 = getPrecedence(operator2);
if(op1 == op2)
return true;
return op1 > op2 ? true: false;
}
int getPrecedence(char op)
{
int weight = 0;
switch(op)
{
case '+':
case '-':
weight = 1;
break;
case '*':
case '/':
weight = 2;
break;
}
return weight;
}
Solution for problem 2 :
// using Linked List
#include <stdio.h>
#include <stdlib.h>
// Node
template <typename T>
typedef struct node {
T data;
// Lower values indicate higher priority
int priority;
struct node* next;
} Node;
// Function to Create A New Node
template <typename T>
Node* newNode(iT d, int p)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = d;
temp->priority = p;
temp->next = NULL;
return temp;
}
// Return the value at head
int peek(Node** head)
{
return (*head)->data;
}
// Removes the element with the
// highest priority form the list
void pop(Node** head)
{
Node* temp = *head;
(*head) = (*head)->next;
free(temp);
}
// Function to push according to priority
template <typename T>
void push(Node** head, T d, int p)
{
Node* start = (*head);
// Create new Node
Node* temp = newNode(d, p);
// Special Case: The head of list has lesser
// priority than new node. So insert new
// node before head node and change head node.
if ((*head)->priority > p) {
// Insert New Node before head
temp->next = *head;
(*head) = temp;
}
else {
// Traverse the list and find a
// position to insert new node
while (start->next != NULL &&
start->next->priority < p) {
start = start->next;
}
// Either at the ends of the list
// or at required position
temp->next = start->next;
start->next = temp;
}
}
// Function to check is list is empty
int isEmpty(Node** head)
{
return (*head) == NULL;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.