Question

Your assignment for this program is to evaluate a numeric expression in postfix notation using a dynamic (pointer based) stack. As stated in the handout, in order to evaluate a numeric expression, a compiler converts an infix numeric expression to postfix notation and then it uses an algorithm and a stack to evaluate the expression. Your program should implement the pseudocode algorithm described in the attached handout.

Your program will read and evaluate expressions stored in an input file (infile.txt). The process will continue until the end of file is read. After each expression is read and evaluated, the expression and its value should be output to a text file using the following format.

                       

                        EXPRESSION: XXXXXXXXXXXXXXXXXXXXXXXXXXX

                        VALUE:XXXXXX

You may assume all expressions in the file will be in postfix notation. You may also assume that the expressions will only have the following operators: +, -, *, /. The variables found in the expressions will be either A, B, C or D. No other variables will be used. The variables should be assigned the following values in your program:

                                    A = 14.0, B = 16.0, C = 20.0, D = 30.0

Assume that all variables will be uppercase. You may store the expression in a string and extract one character at a time. Please use the data file shown below for the program run.

Output your run to another file.

Please note: Your stack should include a working destructor.

infile.dat

DCA-+

ABC-+

ABCD*+A/-

AB-CD+*

Hint: You can use this code to help you input the string and process each character in the string.

while(!in.eof()){

            in>>s; // s is a string, read the entire string on the line

                // process each character in the string using s.length() and a for loop

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

                    //check to see if the character is an operator (+,-,*,/)

                    // or operand A,B,C,D

                    if(s.substr(i,1)==                  ) // use the handout algorithm for the rest

                       

           

           

           

    }

Given s, declared as a string then s.length() returns the number of characters in the string; s.substr(i,1) returns the character in the ith position of the string. The string library contains the length and substr methods; substr(i,n), another method, will return n characters starting at position i of a string.

Answer 1

// C++ program to evaluate the value of postfix expressions

#include <iostream>

#include <string>

#include <fstream>

using namespace std;

// structure of Node of class Stack

struct Node{

               double data;

               Node *next;

};

class Stack{

               Node *top;

public:

               Stack()

               {

                              top = NULL;

               }

               void push(double data)

               {

                              if(top == NULL)

                              {

                                             top = new Node;

                                             top->data = data;

                                             top->next = NULL;

                              }else

                              {

                                             Node *node = new Node;

                                             node->data = data;

                                             node->next = top;

                                             top = node;

                              }

               }

               double pop()

               {

                              if(!isEmpty())

                              {

                                             double data = top->data;

                                             top = top->next;

                                             return data;

                              }

                              return -1;

               }

               bool isEmpty()

               {

                              return(top == NULL);

               }

};

int main() {

               double A = 14.0, B = 16.0, C = 20.0, D = 30.0;

               string s;

               bool invalid;

               ifstream in("infile.dat"); // provide path to input file

               if(in.is_open())

               {

                              Stack stk; // create an object of class Stack

                              ofstream out("outfile.dat"); // provide the path to output file

                              while(!in.eof()){

                                             invalid = false;

                                             in>>s; // s is a string, read the entire string on the line

           // process each character in the string using s.length() and a for loop

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

                                             {

                                                            //check to see if the character is an operator (+,-,*,/)

                                                            // or operand A,B,C,D

// use the handout algorithm for the rest

                                                            if(s.substr(i,1)=="A" || s.substr(i,1) == "B" || s.substr(i,1) == "C" || s.substr(i,1) == "D" ) // if operand, push the corresponding value on the stack

                                                            {

                                                                           if(s.substr(i,1) == "A")

                                                                                          stk.push(A);

                                                                           else if(s.substr(i,1) == "B")

                                                                                          stk.push(B);

                                                                           else if(s.substr(i,1) == "C")

                                                                                          stk.push(C);

                                                                           else

                                                                                          stk.push(D);

                                                            }

                                                            else { // if operator

                                                                           if(stk.isEmpty()) // check if stack is empty

                                                                           {

                                                                                          cout<<" Invalid postfix expression"<<endl;

                                                                                          invalid = true;

                                                                                          break;

                                                                           }

                                                                           // pop the top two operands from stack

                                                                           double op2 = stk.pop();

                                                                           double op1 = stk.pop();

                                                                           // perform the operation and push the value back to stack

                                                                           if(s.substr(i,1) == "+")

                                                                                          stk.push(op1+op2);

                                                                           else if(s.substr(i,1) == "-")

                                                                                          stk.push(op1-op2);

                                                                           else if(s.substr(i,1) == "*")

                                                                                          stk.push(op1*op2);

                                                                           else {

                                                                                          if(op2 != 0)

                                                                                                         stk.push(op1/op2);

                                                                                          else{

                                                                                                         cout<<" Divide by zero error "<<endl;

                                                                                                         invalid = true;

                                                                                                         break;

                                                                                          }

                                                                           }

                                                            }

                                  }

                                             // output to file

                                             if(!stk.isEmpty() && (!invalid))

                                             {

                                                            out<<" EXPRESSION : "<<s<<endl;

                                                            out<<" VALUE : "<<stk.pop()<<endl;

                                             }else{

                                                            out<<" EXPRESSION : "<<s<<endl;

                                                            out<<" Invalid postfix expression"<<endl;

                                             }

                              }

                              //close the files

                              in.close();

                              out.close();

               }else

                              cout<<" Unable to open file : infile.dat"<<endl;

}

//end of program

Output:

Input file:

Output file: