Question

Step 1: Capturing the input

The first step is to write a functionGetInput()that inputs the expression from the keyboard and returns the tokens---the operands and operators---in a queue. You must write this function.

To make the input easier to process, the operands and operators will be separated by one or more spaces, and the expression will be followed by #. For example, here’s a valid input to your program:

6 4 15 * – #

Back in Codio, modify “main.cpp” by defining the following function above main(). Note the additional #include statements, add those as well:

#include <iostream>

#include <stack>

#include <queue>

#include <string>

#include <sstream>

#include <cctype>

using namespace std;

queue<string> GetInput()

{

queue<string> Q;

stringtoken;

cin >> token;

.. // TODO: loop andinputrestof expression, adding to queue. // Do not add the sentinel # to the queue..

return Q;

}

Now modify the main() function to call GetInput, and change the cout statement to output the size of the queue returned by GetInput. This is a simple check to make sure the queue contains the elements of the expression. Build and run, and enter an expression such as

6 4 15 * – #

The output should be a size of 5---3 operands and 2 operators (the # should not be stored in the queue). If you want to be sure the queue is correct, write a quick loop to pop the contents of the queue one by one, and output. When you’re done, comment out these debug output statements.

Step 2: Evaluating the expression (assuming valid input)

Now that the input has been captured, step 2 is to evaluate the expression. The idea is simple: when you see an operand (an integer), push it on a stack. When you see an operator, pop off two operands, perform the operation, and push on the result. When the input has been processed, the answer is on top of the stack. Go ahead and draw out an example on paper and convince yourself it works: 6 4 15 * - should yield -54.

Write a function EvaluatePostfix that takes a queue containing the input, and returns two values: the integer result, and true / false(denoting valid input or not). Here’s the function definition:

bool EvaluatePostfix(queue<string> input, int& result)

{

stack<int> operands;

.. // evaluate expression:.

result = operands.top(); // answer is on top

return true; // successful evaluation

}

For now, assume valid input, and don’t bother with error checking.Loop until the queue is empty, popping one token at a time. Since the tokens are strings, and a string is an array of characters, you can access the first element of a string using[0]. This makes it easy to tell if a token is an integer operand:

string s = input.front();// next token in the queue:

input.pop();

if (isdigit(s[0]))// integer operand:

{

operands.push(stoi(s));// in C++, usestoito convert string to int

}

else // operator{

...

}

To determine the operator, compare s[0] to ‘+’, ‘*’, etc. Once you have the function written, modify main() to call the function and output the result. Build, run and test with a variety of expressions. Here’s a few:

6 4 15 * – # => -54

6 4 –5 * # => 10

21 10 30 * + 80 / # => 4

Step 3: Handling invalid input

The last step is to extend the program to handle invalid input. Modify the EvaluatePostfix function to handle the following:

1. What if the stack contains more than one value at the end (or is empty)? This can happen when the input is empty, or the expression doesn’t contain enough operators. Example: 1 2 3 + #. In this case EvaluatePostfix should return false.

2. What if the stack does not contain 2 operands when an operator is encountered? This can happen when the expression doesn’t contain enough operands. Example: 1 2 + + #. In this case EvaluatePostfix should return false.

3. What if the operator is something other than +,-, * or /. In that case, EvaluatePostfix should return false.

You’ll need to modify main() to check the value returned by EvaluatePostfix. If false is returned, output the word “invalid” followed by a newline. Build, run and test.

Answer 1

Code(Its written using the provided code snippets):

Compiler used: gcc (tdm64-1) 5.1.0

Note: Written in c++ std 11 i.e, compile by configuring ( set flag -std=c++11 for gcc) to your compiler if your compiler requires it.

#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <sstream>
#include <cctype>

using namespace std;

//Fuction to push input to string
queue<string> GetInput()

{

queue<string> Q;

while(true){
    string token;
    cin >> token;
    //ASCII value of # is 35
    //If token == 35 we stop taking input
    if((int)token[0] == 35 ){
        break;
    }
    else{
        Q.push(token);
    }
}

return Q;

}

//Function to evaluate the queue
bool EvaluatePostfix(queue<string> input, int& result){
stack<int> operands;
int operand1;
int operand2;

   while(!input.empty()){
        string temp = input.front();
        //Check if the input is a digit or not
       if (isdigit(temp[0])){
            int value = stoi(temp);
            //cout<<value<<endl;
            operands.push(value);
            input.pop();
        }

        else
        {
            if(operands.empty()){
                //if there are too less operands return false i.e stack is empty
                return false;
            }
            else{
          
                operand1 = operands.top();
                operands.pop();
            }

            if(operands.empty()){
                //if there are too less operands return false i.e stack is empty
                return false;
            }
            else{
                operand2 = operands.top();
                operands.pop();
            }
            //Performing respective arithmetic operation
            if(temp[0] == '+'){
                result = operand2 + operand1;
                operands.push(result);
                input.pop();
            }

            else if(temp[0] == '-'){
                result = operand2 - operand1;
                operands.push(result);
                input.pop();
            }

            else if(temp[0] == '*'){
                result = operand2 * operand1;
                operands.push(result);
                input.pop();
            }

            else if(temp[0] == '/'){
                result = operand2 / operand1;
                operands.push(result);
                input.pop();
            }
            else
            {
                //if operators do not belong to +,-,*,/ the input is incorrect we return false
                return false;
            }
        }
    }

if(operands.size()>1){
    //if stack still has more than 1 value it means there are too few operators or incorrect input, return false
    return false;
}

result = operands.top(); // answer is on top

return true; // successful evaluation

}

int main(){

    queue<string> Q;
    Q = GetInput();
    int result;

    bool eval = EvaluatePostfix(Q,result);

    //if it returns false i.e the input entered is invalid
    if(eval == false){
        cout<<"invalid"<<endl;
    }
    else{
        cout<<result;
    }
  
    return 0;

}

Output:

1.

C:\Users\Documents>.\a.exe
1 2 + + #
invalid

2.

C:\Users\Documents>.\a.exe

1 2 3 + #
invalid

3.

C:\Users\Documents>.\a.exe
6 4 15 * - #
-54

4.

C:\Users\Documents>.\a.exe
21 10 30 * + 80 / #
4

5.

C:\Users\Documents>.\a.exe
6 4 – 5 * #
10