Question

CS 400 Assignment 4
Stack application: postfix expression evaluation.

Description:
- The stack data structure can be used to evaluate postfix expressions. Please refer to the first 14 pages of this tutorial for postfix expression evaluation: http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial2.pdf

Requirement:
- deal with single digit positive integers only. Operands and operators are fully separated by space. 
- learn and use STL stack: http://www.cplusplus.com/reference/stack/stack/
- learn and use isdigit(): http://www.cplusplus.com/reference/cctype/isdigit/  
- take in a postfix arithmetic expression from cin, and evaluate its value. 
- supported operators: +, -, *, /
- for invalid postfix expression, print out an error message and end the program. 
- output the evaluated value of valid expressions. 

Example1: 
- (valid expr) 4 3 - 5 * 
-- push 4 into stack 
-- push 3 into stack 
-- minus operator (-) detected: pop 3 out of stack, as operand_2
-- pop 4 out of stack, as operand_1
-- perform operand_1 minus operand_2, then push the result (1) into stack. 
-- push 5 into stack 
-- multiply operator (*) detected: pop 5 out of stack, as operand_2
-- pop 1 out of stack, as operand_1
-- perform operand_1 times operand_2, then push the result (5) into stack. 
-- input done. check stack value... output final answer: 5

Example2: 
- (invalid expr) 4 4 3 - 5 * is invalid since the stack will have two numbers inside it. 
- (invalid expr) 4 5 5 - / is invalid due to the divide-by-zero error. 

Grading:
- compilable and meaningful attemps: 20 points. 
- correct usage of STL stack: 20 points, including object creation, push(), top() and pop().
- correct postfix expression evaluation: 30 points.
- error handling: 20 points, including divide-by-zero error and invalid expression error
- comments, file_name and indentation: 10 points. 

File_name: 
postfix_eval.cpp

Answer 1

// C++ program to evaluate postfix expression consisting of single digit positive integer and

// operators and operands are fully separated by space

#include <iostream>

#include <stack>

#include <cctype>

using namespace std;

int main() {

       string postfix_exp;

       stack<int> st;

       cout<<"Program to evaluate postfix expression(consisting of single digit positive integers only and Operands and operators are fully separated by space. ) "<<endl;

       // input of postfix expression

       cout<<"Enter the postfix expression : ";

       getline(cin,postfix_exp);

       postfix_exp = postfix_exp.substr(0,postfix_exp.length()-1); // remove '\n' from end

       // loop over the expression

       for(unsigned int i=0;i<postfix_exp.length();i++)

       {

             // check if the character is a digit, then push the int to the stack

             if(isdigit(postfix_exp[i]))

                    st.push((int)(postfix_exp[i]-'0')); // convert the char to int and push it to stack

             else if(!isspace(postfix_exp[i])) // if the character is not a space

             {

                    int n1, n2;

                    // check if stack is empty, then print error and exit

                    if(st.empty())

                    {

                           cout<<"ERROR: Invalid expression "<<endl;

                           return 1;

                    }

                    // if stack is not empty, remove and assign the top element to n2

                    n2 = st.top();

                    st.pop();

                    // check if stack is empty, then print error and exit

                    if(st.empty())

                    {

                           cout<<"ERROR: Invalid expression "<<endl;

                           return 1;

                    }

                    // if stack is not empty, remove and assign the top element to n1

                    n1 = st.top();

                    st.pop();

                    // check the operator

                    if(postfix_exp[i] == '+') // addition

                           st.push(n1+n2); // perform addition and push the result back to stack

                    else if(postfix_exp[i] == '-') // subtraction

                           st.push(n1-n2); // perform n1-n2 and push the result back to stack

                    else if(postfix_exp[i] == '*') // multiplication

                           st.push(n1*n2); // perform multiplication and push the result back to stack

                    else if(postfix_exp[i] == '/') // division

                    {

                           // check if n2 is not zero, then perform n1/n2 and push the result back to stack

                           if(n2 != 0)

                                 st.push(n1/n2);

                           else // if n2 is 0, print error and exit

                           {

                                 cout<<"ERROR: division by zero "<<endl;

                                 return 1;

                           }

                    }else // if any other character found, print error and exit

                    {

                           cout<<"ERROR: Invalid operator "<<endl;

                           return 1;

                    }

             }

       }

       // if stack is empty after scanning the entire expression, print error and exit

       if(st.empty())

             cout<<"ERROR: Invalid expression "<<endl;

       else{

             // get the result from top of stack

             int result = st.top();

             st.pop(); // remove the result from top

             // if stack is non-empty after getting the result, print error and exit else print result

             if(st.empty())

                    cout<<"Result : "<<result<<endl;

             else

                    cout<<"ERROR: Invalid expression "<<endl;

       }

       return 0;

}

//end of program

Output: