Write a C++ program for the following question. The codes are given below. Outpu
ID: 3590815 • Letter: W
Question
Write a C++ program for the following question. The codes are given below. Output exactly the way it's given at the bottom of the question. Greatly appreciate the help.
CODES:
.....................................
LinkedStack.cpp Codes:
......................................
#include <cassert> // For assert
#include "LinkedStack.h" // Header file
LinkedStack::LinkedStack() : topPtr(nullptr)
{
} // end default constructor
LinkedStack::LinkedStack(const LinkedStack& aStack)
{
// Point to nodes in original chain
Node* origChainPtr = aStack.topPtr;
if (origChainPtr == nullptr)
topPtr = nullptr; // Original stack is empty
else
{
// Copy first node
topPtr = new Node();
topPtr->setItem(origChainPtr->getItem());
// Point to first node in new chain
Node* newChainPtr = topPtr;
// Advance original-chain pointer
origChainPtr = origChainPtr->getNext();
// Copy remaining nodes
while (origChainPtr != nullptr)
{
// Get next item from original chain
ItemType nextItem = origChainPtr->getItem();
// Create a new node containing the next item
Node* newNodePtr = new Node(nextItem);
// Link new node to end of new chain
newChainPtr->setNext(newNodePtr);
// Advance pointer to new last node
newChainPtr = newChainPtr->getNext();
// Advance original-chain pointer
origChainPtr = origChainPtr->getNext();
} // end while
newChainPtr->setNext(nullptr); // Flag end of chain
} // end if
} // end copy constructor
LinkedStack::~LinkedStack()
{
// Pop until stack is empty
while (!isEmpty())
pop();
} // end destructor
bool LinkedStack::push(const ItemType& newItem)
{
Node* newNodePtr = new Node(newItem, topPtr);
topPtr = newNodePtr;
newNodePtr = nullptr;
return true;
} // end push
bool LinkedStack::pop()
{
bool result = false;
if (!isEmpty())
{
// Stack is not empty; delete top
Node* nodeToDeletePtr = topPtr;
topPtr = topPtr->getNext();
// Return deleted node to system
nodeToDeletePtr->setNext(nullptr);
delete nodeToDeletePtr;
nodeToDeletePtr = nullptr;
result = true;
} // end if
return result;
} // end pop
ItemType LinkedStack::peek() const
{
assert(!isEmpty()); // Enforce precondition during debugging
// Stack is not empty; return top
return topPtr->getItem();
} // end getTop
bool LinkedStack::isEmpty() const
{
return topPtr == nullptr;
} // end isEmpty
................................................................
LinkedStack.h Codes:
................................................................
#ifndef LINKED_STACK_
#define LINKED_STACK_
#include "Node.h"
class LinkedStack
{
private:
Node* topPtr; // Pointer to first node in the chain;
// this node contains the stack's top
public:
LinkedStack();
LinkedStack(const LinkedStack& aStack); // Copy constructor
~LinkedStack();
bool isEmpty() const;
bool push(const ItemType& newEntry);
bool pop();
ItemType peek() const;
};
#endif
.......................................................
LinkedStackTest.cpp Codes:
.......................................................
#include "LinkedStack.h"
#include <iostream>
using namespace std;
int main()
{
LinkedStack s;
cout << "[1] " << s.isEmpty() << endl;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
cout << "[4] " << s.peek() << endl;
cout << "[0] " << s.isEmpty() << endl;
LinkedStack s2(s);
cout << "[4] " << s2.peek() << endl;
cout << "[0] " << s2.isEmpty() << endl;
s.pop();
cout << "[3] " << s.peek() << endl;
s.push(5);
cout << "[5] " << s.peek() << endl;
s.pop();
s.pop();
s.pop();
s.pop();
cout << "[1] " << s.isEmpty() << endl;
//s.peek();
}
............................................................
Node.cpp Codes:
............................................................
#include "Node.h"
Node::Node() : next(nullptr)
{
} // end default constructor
Node::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor
Node::Node(const ItemType& anItem, Node* nextNodePtr) :
item(anItem), next(nextNodePtr)
{
} // end constructor
void Node::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
void Node::setNext(Node* nextNodePtr)
{
next = nextNodePtr;
} // end setNext
ItemType Node::getItem() const
{
return item;
} // end getItem
Node* Node::getNext() const
{
return next;
} // end getNext
........................................................
Node.h Codes:
.........................................................
#ifndef NODE_
#define NODE_
#include <string>
using namespace std;
typedef int ItemType;
class Node
{
private:
ItemType item; // A data item
Node* next; // Pointer to next node
public:
Node();
Node(const ItemType& anItem);
Node(const ItemType& anItem, Node* nextNodePtr);
void setItem(const ItemType& anItem);
void setNext(Node* nextNodePtr);
ItemType getItem() const ;
Node* getNext() const ;
}; // end Node
#endif
First, look up and familiarize yourself with the STL stack class. You will use this class for this assignment. Implement the Infix to Postfix algorithm discussed in class: string infixToPostfix(string exp) This will take an infix expression as an argument, and return the corresponding postfix expression. Operands will be single upper-case letter, and operators will be ,/+ You may assume the input expression is correct. Your algorithm should skip over any blank spaces it finds. Implement the Postfix Evaluation algorithm discussed in class. double evaluatePostfix (string exp) This will take a postfix expression of the form generated in part 1, and evaluate it as a double value See below for the values of the operands. You will implement an algorithm to convert from postfix to prefix. string postfixToPrefix (string exp) The postfix to prefix conversion algorithm is as follows: Create a stacks, S. of strings Scan the postfix expression From left to right (skip over whitespace) If the character (ch) is an operand: s push (ch) If the character (ch) is an operator, xs-pop) y s.pop () ; s push (chyx) string concatenation) At the end, the resulting prefix string will be the only element in the stack.Explanation / Answer
#include <iostream.h>
#include <stack.h>
#include <string.h>
#include <ctype.h>
using namespace std;
// A utility function to check if the given character is operand
int isOperand(char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
// A utility function to return precedence of a given operator
// Higher returned value means higher precedence
int Prec(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
string infixToPostfix(string exp)
{
int i, k;
// Create a stack of capacity equal to expression size
stack<char> s = new stack<char>;
for (i = 0, k = -1; exp[i]; ++i)
{
// If the scanned character is an operand, add it to output.
if (isOperand(exp[i]))
exp[++k] = exp[i];
// If the scanned character is an ‘(‘, push it to the stack.
else if (exp[i] == '(')
s.push(exp[i]);
// If the scanned character is an ‘)’, pop and output from the stack
// until an ‘(‘ is encountered.
else if (exp[i] == ')')
{
while (!s.empty() && s.peek() != '(')
exp[++k] = s.pop();
if (!s.empty() && s.peek() != '(')
return -1; // invalid expression
else
s.pop();
}
else // an operator is encountered
{
while (!s.empty() && Prec(exp[i]) <= Prec(s.peek()))
exp[++k] = s.pop();
s.push(exp[i]);
}
}
// pop all the operators from the stack
while (s.empty())
exp[++k] = s.pop();
exp[++k] = '';
return exp;
}
double evaluatePostfix(string exp)
{
// Create a stack of capacity equal to expression size
stack<double> s= new stack<double>;
int i;
// Scan all characters one by one
for (i = 0; exp[i]; ++i)
{
if (isdigit(exp[i]))
s.push(exp[i] - '0');
// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
double val1 = s.pop();
double val2 = s.pop();
switch (exp[i])
{
case '+': s.push(val2 + val1); break;
case '-': s.push(val2 - val1); break;
case '*': s.push(val2 * val1); break;
case '/': s.push(val2/val1); break;
}
}
}
return s.pop();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.