Installation and Configuration
Programming Methodology

Evaluate a Mathematical Expression Using Postfix Notation with a Stack in C++

In this C++ exercise, you will implement a stack to evaluate a mathematical expression in postfix notation (also known as Reverse Polish Notation, RPN). The program will read the expression from left to right, pushing operands onto the stack and performing operations when operators are encountered. The result of the expression will be the value left on the stack after all operations are completed.

Group

Data Structures: Stacks, Queues in C++

Objective

1. Create a stack to hold operands during the evaluation of the postfix expression.
2. Traverse through each token of the postfix expression:
- If the token is a number, push it onto the stack.
- If the token is an operator, pop the top two elements from the stack, apply the operator, and push the result back onto the stack.
3. After the full expression has been processed, the result will be the only number left on the stack.
4. Output the result of the expression evaluation.

Implement a stack that calculates the value of a mathematical expression using postfix notation.

Example C++ Exercise

 Copy C++ Code 
#include <iostream>  // Include for input/output operations
#include <stack>      // Include for stack data structure
#include <sstream>    // Include for string stream (used to parse numbers)
#include <string>     // Include for string handling

using namespace std;

// Function to perform arithmetic operations
int performOperation(int operand1, int operand2, char oper) {
    // Perform the operation based on the operator
    switch (oper) {
        case '+': return operand1 + operand2;  // Addition
        case '-': return operand1 - operand2;  // Subtraction
        case '*': return operand1 * operand2;  // Multiplication
        case '/': return operand1 / operand2;  // Division
        default: return 0;  // Default case (should not happen)
    }
}

// Function to evaluate a postfix expression
int evaluatePostfix(string expression) {
    stack<int> s;  // Stack to store operands
    stringstream ss(expression);  // String stream to process each token
    string token;

    while (ss >> token) {  // Read each token in the expression
        if (isdigit(token[0])) {  // If the token is a number
            s.push(stoi(token));  // Push the number onto the stack
        } else {  // If the token is an operator
            int operand2 = s.top();  // Get the second operand
            s.pop();  // Remove the second operand
            int operand1 = s.top();  // Get the first operand
            s.pop();  // Remove the first operand
            int result = performOperation(operand1, operand2, token[0]);  // Perform the operation
            s.push(result);  // Push the result back onto the stack
        }
    }
    return s.top();  // The result is the only number left on the stack
}

// Main function
int main() {
    string expression = "3 4 + 2 * 7 /";  // Example postfix expression
    cout << "Postfix Expression: " << expression << endl;
    int result = evaluatePostfix(expression);  // Evaluate the expression
    cout << "Result: " << result << endl;  // Output the result
    return 0;
}

 Output

Postfix Expression: 3 4 + 2 * 7 /
Result: 2

Share this C++ Exercise


More C++ Programming Exercises of Data Structures: Stacks, Queues in C++

Explore our set of C++ Programming Exercises! Specifically designed for beginners, these exercises will help you develop a solid understanding of the basics of C++. From variables and data types to control structures and simple functions, each exercise is crafted to challenge you incrementally as you build confidence in coding in C++.