Question

How to code up the postfixEval function using the instructions in the comments of the function?...

How to code up the postfixEval function using the instructions in the comments of the function?

// postfixEvalTest.cpp

#include "Token.h"
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// postfix evaluate function prototype

double postfixEval(vector<Token> &expr);

int main() {

  vector<Token> postfix;
  
  postfix.push_back(Token(VALUE,4.0));
  postfix.push_back(Token(VALUE,3.0));
  postfix.push_back(Token(VALUE,2.0));
  postfix.push_back(Token(OPERATOR,'*'));
  postfix.push_back(Token(OPERATOR,'+'));
  postfix.push_back(Token(VALUE,18.0));
  postfix.push_back(Token(VALUE,6.0));
  postfix.push_back(Token(OPERATOR,'/'));
  postfix.push_back(Token(OPERATOR,'-'));

  double result = 0.0;
  //result = postfixEval(postfix);
  
  cout << "The result of 4 3 2 * + 18 6 / - .... is "
       << result << endl;
       
  vector<Token> postfix2;
  
  postfix2.push_back(Token(VALUE,3.0));
  postfix2.push_back(Token(VALUE,7.0));
  postfix2.push_back(Token(VALUE,2.0));
  postfix2.push_back(Token(OPERATOR,'*'));
  postfix2.push_back(Token(OPERATOR,'+'));
  postfix2.push_back(Token(VALUE,8.0));
  postfix2.push_back(Token(VALUE,16.0));
  postfix2.push_back(Token(OPERATOR,'/'));
  postfix2.push_back(Token(OPERATOR,'-'));

  result = 0.0;
  //result = postfixEval(postfix2);
  
  cout << "The result of 3 7 2 * + 8 16 / - .... is "
       << result << endl;
       
  return 0;
}







// postfixEval()   header and body     continued  on the next page





double postfixEval(vector<Token> &expr)
{
   return 0;
   
   // allocate a stack of type double (dstack)
   
   // while not end of vector  // could be a for-loop
   //    1) token = expr[i];  ... what type should "token" be?
   // 
   //    3) switch based upon TokeType of token
   //       a) if its a VALUE
   //            -- push the token value onto the stack
   //       b) if its an OPERATOR
   //          switch based upon the token's character
   //             i) if it's a '+':
   //                [be careful to check for empty stack before 
   //                 calling top() or pop()]
   //                   1) right = dstack.top();  dstack.pop()
   //                   2) same for left
   //                   3) result = left + right;
   //                   4) push result onto dstack
   //             ii) etc.
   //       c) if its anything else ... error
   //
   //  after while loop:
   //
   //  there should only be one value left on the dstack
   //
   //  return it
}
//Token.h

#ifndef TOKEN_H
#define TOKEN_H

#include <iostream>
using namespace std;

enum TokenType { OPEN, CLOSE, OPERATOR, VARIABLE, VALUE, END };

class Token {

public:
        Token (TokenType t, char c) : ttype(t), ch(c) { }
        Token (TokenType t, double d) : ttype(t), number(d) { }
        Token (TokenType t) : ttype(t) { }
        Token () : ttype (END), ch('?'), number(-99999999) { }
        
        TokenType getType() {return ttype;}
        char getChar() {return ch;}
        double getNumber() {return number;}
        
private:
        TokenType ttype;
        char ch;
        double number;
};

ostream & operator << (ostream & os, Token & t) {
        os << "<";
        switch (t.getType()) {
                case OPEN:
                        os << "OPEN," << t.getChar(); break;
                case CLOSE:
                        os << "CLOSE," << t.getChar(); break;
                case OPERATOR:
                        os << "OPER," << t.getChar(); break;
                case VARIABLE:
                        os << "VARI," << t.getChar(); break;
                case VALUE:
                        os << "VALU," << t.getNumber(); break;
                case END:
                        os << "END" ; break;
                default: os << "UNKNOWN";
        }
        os << ">";
        return os;
}               


#endif // TOKEN_H
0 0
Add a comment Improve this question Transcribed image text
Answer #1

We are given two files, postfixEvalTest.cpp and Token.h.

Token.h contains the class definition of Token, the data members, constructors, and the member functions. Also, we are overloading the '<<' operator in order to use it to print the Token given as an argument.

And in postfixEvalTest.cpp, we are given the code to test the postfixEval () function that we need to implement.

Please note that as it was not stated in the problem statement that which operators can be used, we have used +, -, /, and * only. Please add more (in the switch-case block in the code) according to your preferences.  

Let's see how are we going to implement the postfixEval () function using the instructions given in the code as comments:

1. Allocate the stack of type double: We will be able to create a stack of type double (with the name dstack) as we have included the header # include <stack> already.

2. Looping through the vector: We will use a for loop in order to traverse the vector of Tokens provided as the only argument to our function. And do the following in each iteration:

2a. Save the Token element of the vector into a variable of type Token. (Answer for ``what type should "token" be?`` comment)

2b. As the Token element can be a value or an operator, we will use a switch statement to choose what action we need to perform.

2c. In order to find the type of Token we have, we will call the getType() member function of the Token class defined in the Token.h file. And use the return value of getType() function to choose the action.

   i. If getType() returned the VALUE (which is defined as an enumerations(enum) in Token.h file), we will push the token value into stack. We will be able to access the value associated with the token using getNumber() member function of the Token class.

   ii. If getType() returned the OPERATOR (which also is defined as an enumerations(enum) in Token.h file), we will use the switch-case statement again, this time, choose our action based on the operator we have encountered. We can get the operator associated with the token using getChar() member function of the Token class.

   iii. For each operator we find using the getChar() function, we will pop two elements from the stack (before popping from the stack, we must check if the stack is empty using the empty() function of the stack class).

   iv. If we were successfully able to pop two elements from the stack, we will perform the calculation according to what was returned from getChar() function.

a. If getChar() function returned '+', we will add the two popped elements.

b. If getChar() function returned '-', we will subtract the two popped elements.

c. If getChar() function returned '*', we will multiply the two popped elements.

d. If getChar() function returned '/', we will divide the two popped elements.

e. Push the result of the computation into the stack.  

v. If we found any other return value from the getType() function, that means, there is an error. As it is not stated in the question how to indicate the error condition, therefore, when we encounter an error, we will return the value returned by numeric_limits<double> :: min () function, which equals the minimum possible double value which will act as a SENTINEL or a marker, to indicate that the computation couldn't be done because of expression invalid. For using this function, we have included #include <limits> to our postfixEvalTest.cpp file.

3. In the end, we must be left with only one element in the stack, and that is the result of the postfix expression given to us.

4. Therefore, we will return the top of stack.

Please note that we have replaced the comments specified in the code given in the problem statement with our own. The comments given specifies what the next statement or the next block of code is trying to achieve and how it is going to do it.

Here is the full code:

#include "Token.h"
#include <limits>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// postfix evaluate function prototype
double postfixEval(vector<Token> &expr);

int main() {

  vector<Token> postfix;
  
  postfix.push_back(Token(VALUE,4.0));
  postfix.push_back(Token(VALUE,3.0));
  postfix.push_back(Token(VALUE,2.0));
  postfix.push_back(Token(OPERATOR,'*'));
  postfix.push_back(Token(OPERATOR,'+'));
  postfix.push_back(Token(VALUE,18.0));
  postfix.push_back(Token(VALUE,6.0));
  postfix.push_back(Token(OPERATOR,'/'));
  postfix.push_back(Token(OPERATOR,'-'));

  double result = 0.0;
  result = postfixEval(postfix);
  
  cout << "The result of 4 3 2 * + 18 6 / - .... is "
       << result << endl;
       
  vector<Token> postfix2;
  
  postfix2.push_back(Token(VALUE,3.0));
  postfix2.push_back(Token(VALUE,7.0));
  postfix2.push_back(Token(VALUE,2.0));
  postfix2.push_back(Token(OPERATOR,'*'));
  postfix2.push_back(Token(OPERATOR,'+'));
  postfix2.push_back(Token(VALUE,8.0));
  postfix2.push_back(Token(VALUE,16.0));
  postfix2.push_back(Token(OPERATOR,'/'));
  postfix2.push_back(Token(OPERATOR,'-'));

  result = 0.0;
  result = postfixEval(postfix2);
  
  cout << "The result of 3 7 2 * + 8 16 / - .... is "
       << result << endl;
       
  return 0;
}

// Please refer to the typed explanation for better understanding
double postfixEval(vector<Token> &expr)
{
   // allocate a stack of type double (dstack)
   stack <double> dstack;
   
   // traverse the vector of Tokens
   for (int i = 0; i < expr.size(); ++i) {
                
                // save the Token into a variable
            // we will save the expr[i] into a Token variable
                Token token = expr[i];

                // we will switch based on the type of Token we have
                
                // in order to know the type of token, we need to call 
                // the getType () function of the Token class which 
                // returns the type of token    
                switch (token.getType()) {
                                
                        // if the token type was found to be a VALUE
                        // we will push the value associated with the 
                        // token into stack 
                        case VALUE:
                                dstack.push(token.getNumber ());
                                break;

                        // if the token type was found to be an OPERATOR
                        // we will do the following
                        case OPERATOR: 

                                // declare left and right variables
                                double left, right;
                                
                                // switch based upon the token's character
                                // we can get the character using 
                                // getChar () member function of Token class
                                switch (token.getChar ()) {
                                                
                                        // if the operator is '+'
                                        case '+':

                                                // check if stack is empty
                                                if (dstack.empty()) {
                                                        return numeric_limits<double> :: min();   
                                                }
                                                
                                                // get the left token
                                                left = dstack.top();
                                                dstack.pop();

                                                // check if stack is empty
                                                if (dstack.empty()) {
                                                        return numeric_limits<double> :: min();   
                                                }

                                                // get the right token
                                                right = dstack.top();
                                                dstack.pop();

                                                // push the sum into stack
                                                dstack.push(right + left);      

                                                break;

                                        // if the operator is '-'
                                        case '-':

                                                // check if stack is empty
                                                if (dstack.empty()) {
                                                        return numeric_limits<double> :: min();   
                                                }
                                                
                                                // get the left token
                                                left = dstack.top();
                                                dstack.pop();

                                                // check if stack is empty
                                                if (dstack.empty()) {
                                                        return numeric_limits<double> :: min();   
                                                }

                                                // get the right token
                                                right = dstack.top();
                                                dstack.pop();

                                                // push the difference into stack
                                                dstack.push(right - left);      

                                                break;

                                        // if the operator is '*'
                                        case '*':

                                                // check if stack is empty
                                                if (dstack.empty()) {
                                                        return numeric_limits<double> :: min();   
                                                }
                                                
                                                // get the left token
                                                left = dstack.top();
                                                dstack.pop();

                                                // check if stack is empty
                                                if (dstack.empty()) {
                                                        return numeric_limits<double> :: min();   
                                                }

                                                // get the right token
                                                right = dstack.top();
                                                dstack.pop();

                                                // push the product into stack
                                                dstack.push(right * left);      

                                                break;

                                        // if the operator is '/'
                                        case '/':

                                                // check if stack is empty
                                                if (dstack.empty()) {
                                                        return numeric_limits<double> :: min();   
                                                }
                                                
                                                // get the left token
                                                left = dstack.top();
                                                dstack.pop();

                                                // check if stack is empty
                                                if (dstack.empty()) {
                                                        return numeric_limits<double> :: min();   
                                                }

                                                // get the right token
                                                right = dstack.top();
                                                dstack.pop();

                                                // push the quotient into stack
                                                dstack.push(right / left);      

                                                break;
                                }
                }
        }

        return dstack.top();
}

Please note that we have not changed Token.h in any way.

Please refer to the screenshots of the code for understanding indentation of the code.

#include Token.h #include <limits> #include <iostream> #include <vector> #include <stack> using namespace std; // postfix e

vector<Token> postfix2; postfix2.push_back (Token (VALUE,3.0)); postfix2.push_back (Token (VALUE, 7.0)); postfix2.push_back (

// Please refer to the typed explanation for better understanding double postfixEval(vector<Token> &expr) { // allocate a sta

// in order to know the type of token, we need to call // the getType () function of the Token class which // returns the typ

// if the operator is + case +: // check if stack is empty if (dstack.empty()) { return numeric limits double> :: min();

// if the operator is - case .: // check if stack is empty if (dstack.empty()) { return numeric_limits<double> :: min();

// if the operator is * case *: // check if stack is empty if (dstack.empty()) { return numeric_limits double> :: min();

// if the operator is /. case /: // check if stack is empty if (dstack. empty()) { return numeric_limits<double> :: min()

Let's look at the output of our driver code in the main function:

The result of 4 3 2 * + 18 6 / The result of 3 7 2 * + 8 16 / is 7 is 16.5

Add a comment
Know the answer?
Add Answer to:
How to code up the postfixEval function using the instructions in the comments of the function?...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • I need assistance with this code. Is there any way I can create this stack class (dealing with infix to postfix then postfix evaluation) without utilizing <stdio.h> and <math.h>? ________...

    I need assistance with this code. Is there any way I can create this stack class (dealing with infix to postfix then postfix evaluation) without utilizing <stdio.h> and <math.h>? ____________________________________________________________________________________________ C++ Program: #include <iostream> #include <string> #include <stdio.h> #include <math.h> using namespace std; //Stack class class STACK { private: char *str; int N; public: //Constructor STACK(int maxN) { str = new char[maxN]; N = -1; } //Function that checks for empty int empty() { return (N == -1); } //Push...

  • i want similar for this code to solve two questions : 1- Write a program to...

    i want similar for this code to solve two questions : 1- Write a program to convert a postfix expression to infix expression 2-Write a program to convert an infix expression to prefix expression each question in separate code ( so will be two codes ) #include <iostream> #include <string> #define SIZE 50 using namespace std; // structure to represent a stack struct Stack {   char s[SIZE];   int top; }; void push(Stack *st, char c) {   st->top++;   st->s[st->top] = c;...

  • Finish function to complete code. #include <stdio.h> #include <stdlib.h> #include<string.h> #define Max_Size 20 void push(char S[],...

    Finish function to complete code. #include <stdio.h> #include <stdlib.h> #include<string.h> #define Max_Size 20 void push(char S[], int *p_top, char value); char pop(char S[], int *p_top); void printCurrentStack(char S[], int *p_top); int validation(char infix[], char S[], int *p_top); char *infix2postfix(char infix[], char postfix[], char S[], int *p_top); int precedence(char symbol); int main() { // int choice; int top1=0; //top for S1 stack int top2=0; //top for S2 stack int *p_top1=&top1; int *p_top2=&top2; char infix[]="(2+3)*(4-3)"; //Stores infix string int n=strlen(infix); //length of...

  • This code in C converts infix to postfix and evaluates it. The problem is that it...

    This code in C converts infix to postfix and evaluates it. The problem is that it only evaluates one digit expressions. I need to fix it so that it can evaluate 2 digits expressions as well. #include <stdio.h> #include <ctype.h> #include <string.h> #include <math.h> #define SIZE 100 char s[SIZE]; int top=-1; void infixToPostfix(char *infix, char *postfix); void postfixEvaluation(char *postfix); void push(char elem){ s[++top]=elem; } char pop(){ return(s[top--]); } int pr(char elem){ // Order of precedence switch (elem) { case '(':...

  • Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQ...

    Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQUIRED for this program will use two stacks, an operator stack and a value stack. Both stacks MUST be implemented using a linked list. For this program, you are to write functions for the linked list stacks with the following names: int isEmpty (stack); void push (stack, data); data top (stack); void pop (stack); // return TRUE if the stack has no...

  • Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQ...

    Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQUIRED for this program will use two stacks, an operator stack and a value stack. Both stacks MUST be implemented using a linked list. For this program, you are to write functions for the linked list stacks with the following names: int isEmpty (stack); void push (stack, data); data top (stack); void pop (stack); // return TRUE if the stack has no...

  • Help me to fix this code in C language. This code converts infix expressions to postfix and then evaluate the expression...

    Help me to fix this code in C language. This code converts infix expressions to postfix and then evaluate the expression. Right now, it works with single digits. I need to modify it so that it can evaluate expressions with also 2 digits, example: (60+82)%72. Additionally I need to display an error when the parenthesis don't match like (89+8(. I have muted some line that would print the postfix expression with a space like: 22 8 + when the input...

  • If i could get any guidance on how to get this started it will be great....

    If i could get any guidance on how to get this started it will be great. My prof. literally just gave us the information below (which are literally just instructions) and I am unsure on how to get started. For this assignment we are going to create a function that reads an input stream and classifies it into “tokens” from a language that we define here. In this language we make the following rules: ● An identifier is a letter...

  • #include <iostream> #include <string> #include "hashT.h" #include "stateData.h" using namespace std; void stateData::setStateInfo(string sName, string sCapital,...

    #include <iostream> #include <string> #include "hashT.h" #include "stateData.h" using namespace std; void stateData::setStateInfo(string sName, string sCapital,    double stArea, int yAdm, int oAdm) {    stateName = sName; stateCapital = sCapital; stArea = stateArea; yAdm = yearOfAdmission; oAdm = orderOfAdmission;       } void stateData::getStateInfo(string& sName, string& sCapital,    double& stArea, int& yAdm, int& oAdm) {    sName = stateName; sCapital = stateCapital; stArea = stateArea; yAdm = yearOfAdmission; oAdm = orderOfAdmission;       } string stateData::getStateName() { return stateName;...

  • Here is the code I have so far. I'm trying to figure out how to implement...

    Here is the code I have so far. I'm trying to figure out how to implement a boolean and use precedence. The 2nd expression should be 14 but it comes out as 28 so I'm definitely not understanding. #include <stack> #include <iostream> #include <string> using namespace std; // Function to find precedence of // operators. int precedence(char op) {    if (op == '+' || op == '-')        return 1;    if (op == '*' || op ==...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT