Question

Skills needed to complete this assignment: linked lists, stacks

PROMPT (In C++)

Postfix notation is a mathematical notation in which operators follow their operands; for instance, to add 3 and 4 one would write 3 4 + rather than 3 + 4. 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 as 3 4 - 5 + in postfix notation: 4 is first subtracted from 3 and then 5 is added to it. An advantage of postfix notation is that it removes the need for parentheses that are required by infix notation. While 3-4*5 can also be written 3-(4*5), which is difficult from (3-4) * 5. In post fix notation, the former could be written 3 4 5 * -, while the latter could be written 3 4 - 5 * or 5 3 4 - *.

Stacks can be used to evaluate expressions in postfix notations by following these steps: 1. If a number is typed, push it on the stack 2. If an operation is typed, depending on the operation, 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 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 positive numbers only, but the result can be any integer. Only basic operations (+, -, /, *) 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, it has five public member functions: 1. Default constructor: initializes the stack to an empty stack 2. isEmpty: returns true if the stack is empty and false otherwise 3. push: pushes a new number to the top of stack 4. pop: removes the top of the stack 5. top: returns the value at the top of the stack, does not remove it from the stack.

TEMPLATE CODE (MUST USE THIS CODE)

DO NOT edit any other code, only write your code in the sections that say /*your code here*/

#include <iostream> #include <cstdlib> using namespace std; const char SENTINEL = ';';

struct Node { int data; Node *link; };

//precondition: c is initialized //precondition: returns true if c is '+', '-', '*' or '/' bool isOperator(char c); //precondition: o1 and o2 are initialized and op is an operator //precondition: returns op(o1, o2), e.g. if op is '-' then returns o1-o2 int calculate(int o1, in o2, char op); //precondition: c is a digit //precondition: returns the integer value of c int charToInt(char c);

class Stack { public: //default constructor //initializes the stack to an empty stack Stack(); //this is a const function, meaning it cannot change any of the member variables //returns true if the stack is empty, false otherwise bool isEmpty() const; //returns the value at the top of the stack, does not modify the stack, does not check if the stack is empty or not int top() const; //adds data to the top of the stack void push(int data); //removes the top value of stack, does not return it, does nothing if the stack is empty void pop(); private: Note *listHead; //pointer to the head of a linked list };

int main() { char in; Stack operandStack; cout << "Enter a postfix expression (ending with " << SENTINEL << " and press Enter):\n"; cin >> in; while(in != SENTINEL) { if(isOperator(in)) { //pop two numbers from stack int n1, n2; if(operandStack.isEmpty()) { //print error message /*your code here*/ exit(1); } n2 = operandStack.top(); operandStack.pop(); if(operandStack.isEmpty()) { //print error message /*your code here*/ exit(1); } n1 = operandStack.top(); operandStack.pop(); //push the result of calculation to the top of operandStack /*your code here*/ } else { //push the number to the top of operandStack /*your code here*/ } cin >> in; } //pop a number from the top of stack int result; result = operandStack.top(); operandStack.pop(); if(operandStack.isEmpty()) //nothing left in the stack cout << "\nThe result is: " << result << endl; else // there is still numbers in the stack { //print an error message /*your code here*/ } return 0; }

Stack::Stack() { /*your code here*/ }

bool Stack::isEmpty() const { /*your code here*/ }

int Stack::top() const { /*your code here*/ }

void Stack::pop() { /*your code here*/ }

void Stack::push(int data) { /*your code here*/ }

int calculate(int o1, o2, char op) { /*your code here*/ }

bool isOperator(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }

int charToInt(char c) { return(static_cast(c) - static_cast('0'));}

Input/Output Example

Example #1: Enter a postfix expression (ending with ; and press Enter): 3 4 - 5 +; The result is: 4

Example #2 Enter a postfix expression (ending with ; and press Enter): 3 4 - 5; Not enough operators entered!

Example #3 Enter a postfix expression (ending with ; and press Enter): 3 4 - 5 + *; Not enough operands entered for operator: *

Answer 1

Here is your required code in C++

#include <iostream>
#include <cstdlib>

using namespace std;

const char SENTINEL = ';';

struct Node {
int data;
Node *link;
};

//precondition: c is initialized
//precondition: returns true if c is '+', '-', '*' or '/'
bool isOperator(char c);

//precondition: o1 and o2 are initialized and op is an operator
//precondition: returns op(o1, o2), e.g. if op is '-' then returns o1-o2
int calculate(int o1, int o2, char op);

//precondition: c is a digit
//precondition: returns the integer value of c
int charToInt(char c);

class Stack {
  
public:
//default constructor
//initializes the stack to an empty stack
Stack();

//this is a const function, meaning it cannot change any of the member variables
//returns true if the stack is empty, false otherwise
bool isEmpty() const;

//returns the value at the top of the stack, does not modify the stack, does not check if the stack is empty or not
int top() const;

//adds data to the top of the stack
void push(int data);

//removes the top value of stack, does not return it, does nothing if the stack is empty
void pop();

private:
Node *listHead; //pointer to the head of a linked list
};

int main() {

char in;
Stack operandStack;

cout << "Enter a postfix expression (ending with " << SENTINEL << " and press Enter):\n";
cin >> in;

while(in != SENTINEL) {

if(isOperator(in)) { //pop two numbers from stack
int n1, n2;

if(operandStack.isEmpty()) {
//print error message
/*your code here*/
cout<<"Not enough operands entered for operator:"<<in<<endl;
exit(1);

}

n2 = operandStack.top();
operandStack.pop();

if(operandStack.isEmpty()) {
//print error message
/*your code here*/
cout<<"Not enough operands entered for operator:"<<in<<endl;
exit(1);
}

n1 = operandStack.top();
operandStack.pop();

//push the result of calculation to the top of operandStack
/*your code here*/
operandStack.push(calculate(n1, n2, in));

} else {
//push the number to the top of operandStack
/*your code here*/
operandStack.push(charToInt(in));
}
cin >> in;
}

//pop a number from the top of stack
int result;
result = operandStack.top();
operandStack.pop();
if(operandStack.isEmpty()) //nothing left in the stack
cout << "The result is: " << result << endl;
else // there is still numbers in the stack
{
//print an error message
/*your code here*/
cout<<"Not enough operators entered!\n";
}
return 0;
}

Stack::Stack() {
/*your code here*/
listHead = new Node();
}

bool Stack::isEmpty() const {
/*your code here*/
//if(listHead->data==0)
//return true;
return (listHead->link == NULL); //changes
}

int Stack::top() const {
/*your code here*/
return listHead->data;
}

void Stack::pop() {
/*your code here*/

// top assign into temp
Node *temp = listHead;
// assign second node to listHead
listHead = listHead->link;
  
// destroy connection between first and second
temp->link = NULL;
  
// release memory of listHead node
free(temp);

}

void Stack::push(int data) {
/*your code here*/
//if(data==0)
//return; changes
Node* temp = new Node();
  
// check if stack (heap) is full. Then inserting an element would
// lead to stack overflow
if (!temp) {
cout << "\nHeap Overflow";
exit(1);
}
  
// initialize data into temp data field
temp->data = data;
  
// put listHead pointer reference into temp link
temp->link = listHead;
  
// make temp as listHead of Stack
listHead = temp;
}

int calculate(int o1, int o2, char op) {

/*your code here*/
switch(op)
{
case '+' : return (o1 + o2);
break;
case '-' : return (o1 - o2);
break;
case '*' : return (o1 * o2);
break;
case '/' : return (o1 / o2);
break;
}
return -1;
}

bool isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}

int charToInt(char c) {
return(static_cast<int>(c) - static_cast<int>('0'));
}

Please refer to the screenshot of the code to understand the indentation of the code:

Here is the Output for the sample Test Cases:

For test cases related to 0: