Tempelate Code::::: Postfix notation, is a mathematical notation in which operat
ID: 3753544 • Letter: T
Question
Tempelate Code:::::
Postfix notation, is a mathematical notation in which operators follow their operands; for instance, to add 3 and 4, one would write 3 4rather than 3 +4 (infix notation). If there are multiple operations, operators are given immediately after their second operands; so, the expression written 3 - 4 +5 in conventional notation would be written 3 4-5 + in postfix notation: 4 is first subtracted from 3, then 5 is added to the result. An advantage of postfix notation is that it removes the need for parentheses that are required by infix notation. While 3-4 x 5 can also be written 3-(4 x 5), which is different from (3-4) × 5, in postfix notation, the former could be written 3 4 5 x-, while the latter could be written 3 4-5 x or 5 3 4-x (from Wikipedia) Stacks can be used to evaluate expressions in postfix notations by following these steps: . If a number is typed, push it on the stack. If an operation is typed, pop off two numbers from the stack, perform the operation, and push the result back on the stack. You should complete the Stack class and other functions in the template file (found on Carmen) so that when the user enters an expression in postfix notation, the program calculates and shows the result. In this assignment the user enters one-digit numbers only, but the result can be any integer. Only basic operations (i.e. +.-./, *) are entered by the user and integer division is used in calculations. User input ends with a semicolon. Class Stack uses a linked list to implement a stack, and it has five public member functions: Default constructor: initializes the stack to an empty stack isEmpty: retums true if stack is empty and false otherwise push: pushes a new number to the top of stack pop: removes the top of stack, does not return it top: returns the value at the top of stack, does not remove it from staclk There are also two private member function in class Stack for manipulating the internal linked list: headInsert and headRemove (Why they don't have a parameter for head of the list?). These functions are defined as private members because they are not a part of characteristics of a stack. A stack does not have operations for inserting to head of a list or removing from a list. It is just a data structure with a Last In, First Out property. So, we define list-related functions as private members. If we decide at some point to change how we implement the stack internally, e.g. use a vector instead, other programs that use this class do not need to change, because they are only using public members.Explanation / Answer
#include <iostream>
#include <cstdlib>
using namespace std;
const char SENTINEL = ';';
struct Node{
int data;
Node *link;
};
class Stack{
public:
Stack(); // default constructor
// initializes the stack to an empty stack
bool isEmpty() const;// this is a const function , meaning it cannot change any of the member variables
// returns true if stack is empty,false otherwise
int top() const; // this is a const function,meaning it cannot change any of the member variables
// returns the value at the top of stack , does not modify the stack, does not check if the stack if empty or not
void push(int data);
//adds data to the top of the stack
void pop();
// removes the top value of the stack, does not return it, does nothing if the stack is empty
private:
Node *stackTop; // pointer to the head of a linked list
void headInsert(int data);
// precondition : stackTop points to the beginning of a list, could be an empty list
// postcondition : a new node with data is added to the beginning of the list, and stackTop points to the new node
void headRemove();
// precondition : stackTop points to the beginning of the list, could be an empty list
//postcondition : the first node of the list is removed, and stackTop points to the next node
};
bool isOperator(char c);
// precondition : c is initialised
int calculate(int o1,int o2,char op);
int charToInt(char c);
Stack::Stack()
{
stackTop = nullptr;
}
void Stack::headInsert(int data)
{
if(isEmpty())
{
stackTop = new Node;
stackTop->data = data;
stackTop->link = nullptr;
}else{
Node *node =new Node;
node->data = data;
node->link = stackTop;
stackTop = node;
}
}
void Stack::headRemove()
{
if(!isEmpty())
{
Node *node = stackTop;
stackTop = stackTop->link;
delete(node); // release the memory
}
}
bool Stack::isEmpty() const
{
return (stackTop==nullptr);
}
int Stack::top() const
{
return stackTop->data;
}
void Stack::push(int data)
{
headInsert(data);
}
void Stack::pop()
{
headRemove();
}
bool isOperator(char c)
{
return(c=='+' || c=='-' || c=='*' || c=='/');
}
int calculate(int o1,int o2,char op)
{
int res = 0;
switch(op)
{
case '+' : res = o1+o2;
break;
case '-' : res =o1-o2;
break;
case '*' : res = o1*o2;
break;
case '/' : if(o2 != 0)
res = o1/o2;
break;
}
return res;
}
int charToInt(char c)
{
return (static_cast<int>(c)- static_cast<int>('0'));
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.