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

March 24, 2012 admin No comments

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/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
				
						// 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/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
				
						// ============================================================================
//    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/

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

Was this article helpful?

👍 YesNo

Posted in: Advanced, C++, C++, Snippets Tags: array, c++, class, for loop, infix, postfix, stack, template, While Loop

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

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories