Write a function called evaluate_postfix(), with the following signature: int ev

Question

Write a function called evaluate_postfix(), with the following signature:

int evaluate_postfix(string sExp)

This function takes a postfix notation string as input parameter (sExp), and evaluates it and returns its value as an integer.

Your function must support exactly the following four operators and all of their combinations: + - * /.

In your main function, create multiple postfix expressions to thoroughly test your function, like the following:

string s1 = "10 20 + 20 -";
string s2 = "30 2 10 * -";
string s3 = "30 20 10 - -";
string s4 = "30 20 - 10 - ";
cout<

which should create the following output:

10 20 + 20 - = 10
30 2 10 * - = 10
30 20 10 - - = 20
30 20 - 10 - = 0

To evaluate a postfix expression, you need a way to break it into operands and operators. E.g., given s1 above, you need to be able to break it into five strings: "10", "20", "+", "20", and "-". To accomplish this, consider using C++'s stringstream class. As a result, make sure you add a space between all pairs of consecutive operators and operands.

To use stringstream, add header in your code. Then you can use the >> operator to extract space-separated "words", the same way as cout.

string op1, op2, operator;

stringstream ss("10 20 +");

ss >> op1; // 10

ss >> op2; // 20

ss >> operator; // +

You also need a way to convert from a string representation to an integer, and back. Use the following two functions that I wrote:

// converts string to integer

int strToInt(string op){
int i=0;
stringstream number(op);
number>>i;
return i;
}

// converts from integer to string
string intToStr(int i){
stringstream ss;
ss< return ss.str();
}

Explanation / Answer

include <ctype.h>

#include <string.h>

#include <iostream.h>

#include "stack.h"

void main()

//Evaluates postfix expression

{

Stack OpStack;               //stack of integers

const StrLength = 20;

char Expression[StrLength]; //expression to be evaluated

char NextCh;                 //next data character

int Index;                   //index of next character

int Op1;                     //operand values

int Op2;

int NewOp;                   //new operand for stack

int Result;                  //result of operator evaluation

int Success;                 //flag for stack operation

char IntString[StrLength];   //integer string representation

cout << "Enter your expression > ";

cin.getline(Expression, StrLength, ' ');

Index = 0;

Success = True;

while (Success && (Index < strlen(Expression)))

{

    //invariant:

    // OpStack contains all unprocessed operands and results;

    // Index <= strlen(Expression) + 1

    NextCh = Expression[Index]; //get next character

    //isdigit() from ctype.h checks if character is digit 0-9

    if (isdigit(NextCh))

    {

      GetInteger(Expression, Index, NewOp); //get value

      OpStack.Push(NewOp, Success);          //push value

      if (!Success)

        cout<< "Stack overflow error. ";

    }

    else if ((NextCh == '+') || (NextCh == '-') ||

                (NextCh == '*') || (NextCh == '/'))

    {

      OpStack.Pop(Op2, Success);

      OpStack.Pop(Op1, Success);

      if (!Success)

        cout << "Invalid expression. ";

      else

      {

        Result = Eval(NextCh, Op1, Op2);

        OpStack.Push(Result, Success);

        if (!Success)

          cout << "Stack overflow ";

      }

    }

    Index++;                            //next character

}

if (Success)

    OpStack.Pop(Result, Success);       //get result

if ((Success) && (OpStack.IsEmpty()))

    cout << "Expression value is " << Result << ' ';

else

    cout << "Invalid expression. ";

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.