How to Evaluate a Postfix Expression using Stack in C++?
The type of expression in which a pair of operands is followed by an operator is called a postfix expression. In this article, we will learn how we can use the stack data structure to evaluate the value of a postfix expression in C++.
Example:
Input: Postfix expression: "73*4+"
Output: 25
Evaluating Postfix Expression Using a Stack in C++
To evaluate a postfix expression, we can use the std::stack by following the below approach.
Approach
- Create an empty stack of integers.
- Iterate through each character of the postfix expression, and check if the character is Operand or Operator.
- If the character is a digit (operand), convert it to an integer and push it onto the stack.
- If the character is an operator, pop the top two elements from the stack (considered as operands), perform the operation, and push the result back onto the stack.
- After the iteration is over, the top of the stack will contain the result of the postfix expression. Return this value.
C++ Program to Use a Stack to Evaluate a Postfix Expression in C++
The following program illustrates how we can use a stack to evaluate a postfix expression in C++.
// C++ Program to illustrate how we can use the stack data
// structure to evaluate the value of a postfix expression
#include <iostream>
#include <stack>
#include <string>
using namespace std;
// Function to perform an operation based on the operator
// and return the result
int performOperation(int operand1, int operand2,
char operation)
{
switch (operation) {
case '+':
return operand1 + operand2;
case '-':
return operand1 - operand2;
case '*':
return operand1 * operand2;
case '/':
return operand1 / operand2;
default:
return 0;
}
}
// Function to evaluate the postfix expression
int evaluatePostfixExpression(const string& expression)
{
stack<int> stack;
for (char c : expression) {
if (isdigit(c)) {
// Convert char digit to int and push onto the
// stack
stack.push(c - '0');
}
else {
// Pop the top two elements for the operation
int operand2 = stack.top();
stack.pop();
int operand1 = stack.top();
stack.pop();
// Perform operation and push the result back
// onto the stack
int result
= performOperation(operand1, operand2, c);
stack.push(result);
}
}
// The final result should be the only item left in the
// stack
return stack.top();
}
int main()
{
string expression2 = "73*4+";
int result = evaluatePostfixExpression(expression2);
cout << "Result of Postfix Expression \"" << expression2
<< "\" is: " << result << endl;
return 0;
}
Output
Result of Postfix Expression "73*4+" is: 25
Time complexity: O(N), here N is the length of the postfix expression.
Auxilliary Space: O(N)
Contact Us