Question

Skills needed to complete this assignment: linked lists, stacks.

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 (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 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 different from (3 − 4) × 5. In postfix 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: • If a number is typed, push it on the stack. • 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 (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 positive 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: returns true if the stack is empty and false otherwise

• push: pushes a new number to the top of stack

• pop: removes the top of stack

• top: returns the value at the top of stack, does not remove it from stack

You must use the template file and only add you code were you see /*your code here*/. Do not modify other parts of the code. Do not use C/C++ libraries other than iostream and cstdlib.

template code

#include <iostream>
#include <cstdlib>

using namespace std;

const char SENTINEL = ';';

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

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

// precondition: o1 and o2 are initialized and op is an operator
// postcondition: 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
// postcondition: 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;

// 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 is empty or not
int top() const;

// adds data to the top of 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()) {
// pring error message
/*your code here*/

exit(1);
}
n2 = operandStack.top();
operandStack.pop();

if (operandStack.isEmpty()) {
// pring 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 opernadStack
/*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 are still numbers in the stack
{
// pring 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, int o2, char op) {
/*your code here*/
}

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

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

Answer 1

// C++ program to evaluate the postfix expression using Stack
#include <iostream>
#include <cstdlib>
using namespace std;

const char SENTINEL = ';';

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

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

// precondition: o1 and o2 are initialized and op is an operator
// postcondition: 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
// postcondition: 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;

// 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 is empty or not
int top() const;

// adds data to the top of 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

       cout<<"ERROR: Invalid postfix expression"<<endl;
       exit(1);
   }
   n2 = operandStack.top();
   operandStack.pop();

   if (operandStack.isEmpty()) {
   // print error message

       cout<<"ERROR: Invalid postfix expression"<<endl;
       exit(1);
   }
   n1 = operandStack.top();
   operandStack.pop();

   // push the result of calculation to the top of operandStack

   operandStack.push( calculate(n1 ,n2,in));

   } else {
   // push the number to the top of opernadStack
       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 << "\nThe result is: " << result << endl;
   else // there are still numbers in the stack
   {
       // print an error message
cout<<"ERROR: Invalid postfix expression"<<endl;

   }
   return 0;
}

Stack::Stack() {
   listHead = NULL;
}

bool Stack::isEmpty() const {

   return(listHead == NULL);
}

int Stack::top() const {

   if(!isEmpty())
       return listHead->data;
   return 0;
}

void Stack::pop() {

   Node *node = listHead;
   listHead = listHead->link;
   delete(node);
}

void Stack::push(int data) {

   Node *node = new Node;
   node->data = data;
   node->link = listHead;
   listHead = node;
}

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

   if(op == '+')
       return o1+o2;
   else if(op == '-')
       return o1-o2;
   else if(op == '*')
       return o1*o2;
   else
   {
       if(o2 == 0)
       {
           cout<<"ERROR: divide by 0 "<<endl;
           exit(1);      
}
       else
           return(o1/o2);
   }
}

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

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

}
//end of program

Output: