Evaluating postfix expressions (also known as Reverse Polish Notation) is a common problem in computer science, particularly in the domain of compilers and calculators. A postfix expression is a mathematical notation in which every operator follows all of its operands, eliminating the need for parentheses to dictate the order of operations. This comprehensive guide will explore how to evaluate postfix expressions using C++ through three different solutions, each with detailed explanations and outputs. Before diving into the examples, let’s review the prerequisites necessary for this article.
Prerequisites
To follow along with this guide, you should have:
- Basic knowledge of C++ programming
- A C++ compiler installed on your machine
- Familiarity with stack data structures and standard template libraries (STL)
1. Using a Stack Data Structure
1.1. Example 1: Evaluating a Simple Postfix Expression
In this example, we will use a stack to evaluate a simple postfix expression.
Code
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
int evaluatePostfix(const std::string &expression) {
std::stack<int> stack;
for (char ch : expression) {
if (isdigit(ch)) {
stack.push(ch - '0');
} else {
int operand2 = stack.top(); stack.pop();
int operand1 = stack.top(); stack.pop();
switch (ch) {
case '+': stack.push(operand1 + operand2); break;
case '-': stack.push(operand1 - operand2); break;
case '*': stack.push(operand1 * operand2); break;
case '/': stack.push(operand1 / operand2); break;
}
}
}
return stack.top();
}
int main() {
std::string expression = "231*+9-";
int result = evaluatePostfix(expression);
std::cout << "Postfix Evaluation of " << expression << " is " << result << std::endl;
return 0;
}
Explanation
- Stack Initialization: We initialize a stack to store operands.
- Digit Check: We check if the character is a digit and push it onto the stack.
- Operator Check: We pop two operands from the stack, perform the operation, and push the result back onto the stack.
- Final Result: The final result of the expression is the top element of the stack.
- Testing: We test the function with the expression “231*+9-” and print the result.
Output
Postfix Evaluation of 231*+9- is -4
1.2. Example 2: Handling Multi-Digit Operands
In this example, we modify the function to handle multi-digit operands in the postfix expression.
Code
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <sstream>
int evaluatePostfix(const std::string &expression) {
std::stack<int> stack;
std::istringstream tokens(expression);
std::string token;
while (tokens >> token) {
if (isdigit(token[0])) {
stack.push(std::stoi(token));
} else {
int operand2 = stack.top(); stack.pop();
int operand1 = stack.top(); stack.pop();
switch (token[0]) {
case '+': stack.push(operand1 + operand2); break;
case '-': stack.push(operand1 - operand2); break;
case '*': stack.push(operand1 * operand2); break;
case '/': stack.push(operand1 / operand2); break;
}
}
}
return stack.top();
}
int main() {
std::string expression = "10 20 + 30 40 + *";
int result = evaluatePostfix(expression);
std::cout << "Postfix Evaluation of \"" << expression << "\" is " << result << std::endl;
return 0;
}
Explanation
- String Stream: We use a
std::istringstreamto tokenize the input string. - Multi-Digit Handling: We convert the token to an integer if it is a digit.
- Operator Handling: We perform the operations as before and push the result onto the stack.
- Testing: We test the function with the expression “10 20 + 30 40 + *” and print the result.
Output
Postfix Evaluation of "10 20 + 30 40 + *" is 2100
2. Using Class and Inheritance
2.1. Example 3: Using a Class-Based Approach
In this example, we use a class-based approach to encapsulate the logic for evaluating a postfix expression.
Code
#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <vector>
class PostfixEvaluator {
public:
int evaluate(const std::string &expression) {
std::stack<int> stack;
std::istringstream tokens(expression);
std::string token;
while (tokens >> token) {
if (isdigit(token[0])) {
stack.push(std::stoi(token));
} else {
int operand2 = stack.top(); stack.pop();
int operand1 = stack.top(); stack.pop();
switch (token[0]) {
case '+': stack.push(operand1 + operand2); break;
case '-': stack.push(operand1 - operand2); break;
case '*': stack.push(operand1 * operand2); break;
case '/': stack.push(operand1 / operand2); break;
}
}
}
return stack.top();
}
};
int main() {
PostfixEvaluator evaluator;
std::vector<std::string> expressions = {"10 20 +", "5 1 2 + 4 * + 3 -", "10 20 + 30 40 + *"};
for (const auto &expression : expressions) {
int result = evaluator.evaluate(expression);
std::cout << "Postfix Evaluation of \"" << expression << "\" is " << result << std::endl;
}
return 0;
}
Explanation
- Class Definition: We define a class
PostfixEvaluatorwith anevaluatemethod to encapsulate the logic. - Evaluation Logic: The evaluation logic is similar to the previous example, using a stack to perform the operations.
- Testing: We test the function with multiple expressions and print the results.
Output
Postfix Evaluation of "10 20 +" is 30
Postfix Evaluation of "5 1 2 + 4 * + 3 -" is 14
Postfix Evaluation of "10 20 + 30 40 + *" is 2100
Conclusion
In this comprehensive guide, we explored various methods to evaluate a postfix expression using C++. We demonstrated how to use a stack data structure for simple and multi-digit operands, and how to encapsulate the logic using a class-based approach. Each method offers a unique approach to solving the problem, catering to different needs and complexities. By mastering these techniques, you can efficiently evaluate postfix expressions in C++, enhancing your data processing and algorithm development skills.