## C++ || Stack Based Postfix Evaluation (Single Digit)

This page consists of another homework assignment which was presented in a C++ Data Structures course. While the previously discussed program dealt with converting Infix expressions to Postfix, this program will demonstrate exactly how to evaluate them.

NOTE: Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!

REQUIRED KNOWLEDGE FOR THIS PROGRAM

```What Is Postfix? How To Convert Infix To Postfix Equations Stack Data Structure Cin.getline How To Evaluate Postfix Expressions The Order Of Operations #include "ClassStackType.h" ```

The title of this page is called – “Stack Based Postfix Evaluation (Single Digit).” Why “single digit?” The program demonstrated on this page has the ability to evaluate a postfix equation, but it only has the ability to evaluate single digit values. What do I mean by that? Consider the infix equation: 5+2. When that expression is converted to postfix, it will come out to be: 52+, and the answer will be 7 (5+2=7). But what if we have an equation like 12+2? When that expression is converted to postfix, it will come out to be: 122+. The postfix conversion is correct, but when you try to evaluate the expression, we do not know if the math operation should be 12+2 or 1+22, it can be read either way.

Question: So why is this program being displayed if it only works for single digits?
Answer: Because it demonstrates the process of evaluating postfix equations very well.

Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!

Before we get into things, here is a helpful algorithm for evaluating a postfix expression in pseudo code:

``` // An algorithm for postfix evaluation. // For example, (1 + 2) / (5 + 6) translates to 1 2 + 5 6 + / // which equals the result of 0.272727 // Valid operands are single digits: 0-9 // Valid operators are: +, -, *, /, ^, \$ // Highest precedence: ^, \$ // Lowest precedence: +,- // the operators ')' and '('never goes on stack. double EvaluatePostfix(string postfix) { while there is input { if input is a number push current number on stack else if input is a math operator and stack is not empty set operand2 to the top of the operand stack pop the stack set operand1 to the top of the operand stack pop the stack apply the math operation that represents to operand1 and operand2 push the result onto the stack else error } // When the loop is finished, the operand stack will contain one item, // the result of evaluating the expression pop the stack return the answer to the caller }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829 // An algorithm for postfix evaluation.// For example,  (1 + 2) / (5 + 6) translates to  1 2 + 5 6 + /// which equals the result of 0.272727// Valid operands are single digits: 0-9// Valid operators are: +, -, *, /, ^, \$// Highest precedence: ^, \$// Lowest precedence: +,-// the operators ')' and '('never goes on stack. double EvaluatePostfix(string postfix){  while there is input  {    if input is a number        push current number on stack    else if input is a math operator and stack is not empty        set operand2 to the top of the operand stack            pop the stack        set operand1 to the top of the operand stack            pop the stack        apply the math operation that represents to operand1 and operand2            push the result onto the stack    else error  }  // When the loop is finished, the operand stack will contain one item,  // the result of evaluating the expression  pop the stack  return the answer to the caller}// http://programmingnotes.org/ ```

Once you understand the process of converting from infix to postfix, adding the ability to evaluate multiple digits within this program should be doable.

======= POSTFIX EVALUATION =======

This program uses a custom template.h class. To obtain the code for that class, click here.

``` Postfix Evaluation (Single Digit) C++ // ============================================================================ // Author: Kenneth Perkins // Date: Mar 24, 2012 // Taken From: http://programmingnotes.org/ // File: PostfixEvaluation.cpp // Description: Demonstrate the use of a stack based postfix evaluation. // ============================================================================ #include <iostream> #include <cstdlib> #include <cmath> #include "ClassStackType.h" using namespace std; // function prototypes void DisplayDirections(); double EvaluatePostfix(char* postfix); bool IsMathOperator(char token); double DoMath(double op1, double op2, char token); int main() { // declare variables char expression[50]; // array holding the postfix data double answer = 0; // display directions to user DisplayDirections(); // get data from user cout<<"\nPlease enter a postfix expression: "; cin.getline(expression, sizeof(expression)); cout <<"\nThe postfix expression = "<<expression<<endl; cout<<"\nCalculations:\n"; answer = EvaluatePostfix(expression); cout<<"\nFinal answer = "<<answer<<endl; return 0; }// end of main void DisplayDirections() { cout << "\n==== Postfix Evaluation ====\n" <<"\nMath Operators:\n" <<"+ || Addition\n" <<"- || Subtraction\n" <<"* || Multiplication\n" <<"/ || Division\n" <<"% || Modulus\n" <<"^ || Power\n" <<"\$ || Square Rootn\n" <<"Sample Postfix Equation: 45^14*232+\$2-/12%24*/* \n"; }// end of DisplayDirections double EvaluatePostfix(char* postfix) { // declare function variables int counter = 0; int currentNum = 0; char token = 'a'; double op1 = 0; double op2 = 0; double answer = 0; StackType<double> doubleStack; // loop thru array until there is no more data while(postfix[counter] != '\0') { // push numbers onto the stack if(isdigit(postfix[counter])) { currentNum = postfix[counter] - '0'; doubleStack.Push(currentNum); } else if(isspace(postfix[counter])) { // DO NOTHING } // if expression is a math operator, pop numbers from stack // & send the popped numbers to the 'DoMath' function else if((IsMathOperator(postfix[counter])) && (!doubleStack.IsEmpty())) { token = postfix[counter]; // if expression is square root operation // only pop stack once if(token == '\$') { op2 = 0; op1 = doubleStack.Top(); doubleStack.Pop(); answer = DoMath(op1,op2,token); doubleStack.Push(answer); } else { op2 = doubleStack.Top(); doubleStack.Pop(); op1 = doubleStack.Top(); doubleStack.Pop(); answer = DoMath(op1,op2,token); doubleStack.Push(answer); } } else { cout<<"\nINVALID INPUT\n"; exit(1); } ++counter; } // pop the final answer from the stack, and return to main answer = doubleStack.Top(); doubleStack.Pop(); return answer; }// end of EvaluatePostfix bool IsMathOperator(char token) {// this function checks if operand is a math operator switch(token) { case '+': return true; break; case '-': return true; break; case '*': return true; break; case '/': return true; break; case '%': return true; break; case '^': return true; break; case '\$': return true; break; default: return false; break; } }// end of IsMathOperator double DoMath(double op1, double op2, char token) {// this function carries out the actual math process double ans = 0; switch(token) { case '+': cout<<op1<<token<<op2<<" = "; ans = op1 + op2; break; case '-': cout<<op1<<token<<op2<<" = "; ans = op1 - op2; break; case '*': cout<<op1<<token<<op2<<" = "; ans = op1 * op2; break; case '/': cout<<op1<<token<<op2<<" = "; ans = op1 / op2; break; case '%': cout<<op1<<token<<op2<<" = "; ans = (int)op1 % (int)op2; break; case '^': cout<<op1<<token<<op2<<" = "; ans = pow(op1, op2); break; case '\$': cout<<char(251)<<op1<<" = "; ans = sqrt(op1); break; default: ans = 0; break; } cout<<ans<<endl; return ans; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194 // ============================================================================//    Author: Kenneth Perkins//    Date:   Mar 24, 2012//    Taken From: http://programmingnotes.org///    File:  PostfixEvaluation.cpp//    Description: Demonstrate the use of a stack based postfix evaluation.// ============================================================================#include <iostream>#include <cstdlib>#include <cmath>#include "ClassStackType.h"using namespace std; // function prototypesvoid DisplayDirections();double EvaluatePostfix(char* postfix);bool IsMathOperator(char token);double DoMath(double op1, double op2, char token); int main(){     // declare variables     char expression[50]; // array holding the postfix data     double answer = 0;      // display directions to user     DisplayDirections();      // get data from user     cout<<"\nPlease enter a postfix expression: ";     cin.getline(expression, sizeof(expression));      cout <<"\nThe postfix expression = "<<expression<<endl;      cout<<"\nCalculations:\n";      answer = EvaluatePostfix(expression);      cout<<"\nFinal answer = "<<answer<<endl;      return 0;}// end of main void DisplayDirections(){     cout << "\n==== Postfix Evaluation ====\n"         <<"\nMath Operators:\n"         <<"+ || Addition\n"         <<"- || Subtraction\n"         <<"* || Multiplication\n"         <<"/ || Division\n"         <<"% || Modulus\n"         <<"^ || Power\n"         <<"\$ || Square Rootn\n"         <<"Sample Postfix Equation: 45^14*232+\$2-/12%24*/* \n";}// end of DisplayDirections double EvaluatePostfix(char* postfix){    // declare function variables    int counter = 0;    int currentNum = 0;    char token = 'a';    double op1 = 0;    double op2 = 0;    double answer = 0;    StackType<double> doubleStack;     // loop thru array until there is no more data    while(postfix[counter] != '\0')    {        // push numbers onto the stack        if(isdigit(postfix[counter]))        {            currentNum = postfix[counter] - '0';            doubleStack.Push(currentNum);        }        else if(isspace(postfix[counter]))        {            // DO NOTHING        }        // if expression is a math operator, pop numbers from stack        // & send the popped numbers to the 'DoMath' function        else if((IsMathOperator(postfix[counter])) && (!doubleStack.IsEmpty()))        {            token = postfix[counter];             // if expression is square root operation            // only pop stack once            if(token == '\$')            {                op2 = 0;                op1 = doubleStack.Top();                doubleStack.Pop();                 answer = DoMath(op1,op2,token);                doubleStack.Push(answer);            }            else            {                op2 = doubleStack.Top();                doubleStack.Pop();                op1 = doubleStack.Top();                doubleStack.Pop();                 answer = DoMath(op1,op2,token);                doubleStack.Push(answer);            }        }        else        {            cout<<"\nINVALID INPUT\n";            exit(1);        }        ++counter;    }    // pop the final answer from the stack, and return to main    answer = doubleStack.Top();    doubleStack.Pop();     return answer;}// end of EvaluatePostfix bool IsMathOperator(char token){// this function checks if operand is a math operator     switch(token)     {        case '+':            return true;            break;        case '-':            return true;            break;        case '*':            return true;            break;        case '/':            return true;            break;        case '%':            return true;            break;        case '^':            return true;            break;        case '\$':            return true;            break;        default:            return false;            break;     }}// end of IsMathOperator double DoMath(double op1, double op2, char token){// this function carries out the actual math process    double ans = 0;    switch(token)    {        case '+':            cout<<op1<<token<<op2<<" = ";            ans = op1 + op2;            break;        case '-':            cout<<op1<<token<<op2<<" = ";            ans = op1 - op2;            break;        case '*':            cout<<op1<<token<<op2<<" = ";            ans = op1 * op2;            break;        case '/':            cout<<op1<<token<<op2<<" = ";            ans = op1 / op2;            break;        case '%':            cout<<op1<<token<<op2<<" = ";            ans = (int)op1 % (int)op2;            break;        case '^':            cout<<op1<<token<<op2<<" = ";            ans = pow(op1, op2);            break;        case '\$':            cout<<char(251)<<op1<<" = ";            ans = sqrt(op1);            break;        default:            ans = 0;            break;    }    cout<<ans<<endl;    return ans;}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output
(Note: the code was compile three separate times to display different output)

`====== RUN 1 ======`

``` ==== Postfix Evaluation ==== Math Operators: + || Addition - || Subtraction * || Multiplication / || Division % || Modulus ^ || Power \$ || Square Root Sample Postfix Equation: 45^14*232+\$2-/12%24*/* Please enter a postfix expression: 1 2 + 5 6 + / The postfix expression = 1 2 + 5 6 + / Calculations: 1+2 = 3 5+6 = 11 3/11 = 0.272727 Final answer = 0.272727 ====== RUN 2 ====== ==== Postfix Evaluation ==== Math Operators: + || Addition - || Subtraction * || Multiplication / || Division % || Modulus ^ || Power \$ || Square Root Sample Postfix Equation: 45^14*232+\$2-/12%24*/* Please enter a postfix expression: 35*76^+ The postfix expression = 35*76^+ Calculations: 3*5 = 15 7^6 = 117649 15+117649 = 117664 Final answer = 117664 ====== RUN 3 ====== ==== Postfix Evaluation ==== Math Operators: + || Addition - || Subtraction * || Multiplication / || Division % || Modulus ^ || Power \$ || Square Root Sample Postfix Equation: 45^14*232+\$2-/12%24*/* Please enter a postfix expression: 45^4*32+\$2-/12%24*/* The postfix expression = 45^4*32+\$2-/12%24*/* ```

```Calculations: 4^5 = 1024 1024*4 = 4096 3+2 = 5 √5 = 2.23607 2.23607-2 = 0.236068 4096/0.236068 = 17350.9 1%2 = 1 2*4 = 8 1/8 = 0.125 17350.9*0.125 = 2168.87 Final answer = 2168.87 ```