Evaluating a Postfix Expression Using a Stack -Code C++

Code

#include <iostream>
#include <stack>
#include <cmath> // For exponentiation operator (^)

using namespace std;

// Function to evaluate a postfix expression
double evaluatePostfixExpression(string postfix) {
    stack<double> operands; // Stack to store operands during evaluation

    for (char c : postfix) {
        if (isdigit(c)) {
            // If character is a digit (operand), convert it to double and push onto the stack
            double operand = c - '0';
            operands.push(operand);
        } else if (c == '^') {
            // If character is the exponentiation operator, '^'
            // Pop the top two operands from the stack
            double op2 = operands.top();
            operands.pop();
            double op1 = operands.top();
            operands.pop();

            // Apply exponentiation operation and push the result back onto the stack
            double result = pow(op1, op2);
            operands.push(result);
        } else {
            // If character is an operator ('+', '-', '*', '/')
            // Pop the top two operands from the stack
            double op2 = operands.top();
            operands.pop();
            double op1 = operands.top();
            operands.pop();

            // Apply the corresponding operation based on the operator and push the result back onto the stack
            switch (c) {
                case '+':
                    operands.push(op1 + op2); // Addition
                    break;
                case '-':
                    operands.push(op1 - op2); // Subtraction
                    break;
                case '*':
                    operands.push(op1 * op2); // Multiplication
                    break;
                case '/':
                    operands.push(op1 / op2); // Division
                    break;
            }
        }
    }

    // The final result is the top element of the stack
    return operands.top();
}

int main() {
    string postfixExpression = "43+5*"; // Example postfix expression
    double result = evaluatePostfixExpression(postfixExpression); // Evaluate the postfix expression
    cout << "Postfix Expression: " << postfixExpression << endl; // Print the postfix expression
    cout << "Result: " << result << endl; // Print the result

    return 0;
}

Output

Explaining:

#include <iostream>
#include <stack>
#include <cmath> // For exponentiation operator (^)

1. #include <stack> is used to include the stack library, which provides the stack data structure.

2. #include <cmath> is used to include the math library for using mathematical functions like pow() in the code.

// Function to evaluate a postfix expression
double evaluatePostfixExpression(string postfix) {
    stack<double> operands; // Stack to store operands during evaluation

    for (char c : postfix) {
        //value given in function stored in char c
        if (isdigit(c)) {
            // If character is a digit (operand), convert it to double and push onto the stack
            double operand = c - '0'; //acc to ASCI code 0 = 48 so we will conver it into asci
            operands.push(operand); //operand is pushed into operands stack
        } else if (c == '^') {
            // If character is the exponentiation operator, '^'
            // Pop the top two operands from the stack
            double op2 = operands.top();
            operands.pop();
            double op1 = operands.top();
            operands.pop();

            // Apply exponentiation operation and push the result back onto the stack
            double result = pow(op1, op2);
            operands.push(result);
        }

1. stack<double> operands;: This creates a stack named operands to store the operands during the evaluation of the postfix expression.

2. for (char c : postfix) {: This is a loop that iterates over each character c in the postfix string.

3. if (isdigit(c)) {: This condition checks if the current character c is a digit (an operand).

4. double operand = c - '0';: If c is a digit, it subtracts the ASCII value of '0' from c to convert it to the corresponding numeric value and assigns it to the operand variable.

5. operands.push(operand);: The operand is pushed onto the operands stack.

6. else if (c == '^') {: This condition checks if the current character c is the exponentiation operator '^'.

7. double op2 = operands.top();: If c is the exponentiation operator, it retrieves the top operand (op2) from the operands stack.

8. operands.pop();: The top operand is removed from the stack.

9. double op1 = operands.top();: The next top operand (op1) is retrieved from the stack.

10. operands.pop();: The next top operand is removed from the stack.

11. double result = pow(op1, op2);: The exponentiation operation is performed on op1 raised to the power of op2, and the result is stored in the result variable.

12. operands.push(result);: The result is pushed back onto the operands stack.

else {
            // If character is an operator ('+', '-', '*', '/')
            // Pop the top two operands from the stack
            double op2 = operands.top();
            operands.pop();
            double op1 = operands.top();
            operands.pop();

            // Apply the corresponding operation based on the operator and push the result back onto the stack
            switch (c) {
                case '+':
                    operands.push(op1 + op2); // Addition
                    break;
                case '-':
                    operands.push(op1 - op2); // Subtraction
                    break;
                case '*':
                    operands.push(op1 * op2); // Multiplication
                    break;
                case '/':
                    operands.push(op1 / op2); // Division
                    break;
            }
        }
    }

the else block is executed when the character c is an operator ('+', '-', '*', '/'). Here's an explanation of how it works:

1. The top two operands from the operands stack are popped and stored in variables op2 and op1, respectively. The order of popping is important because the second operand popped (op2) will be the one that appears later in the postfix expression.

2. After popping the operands, the corresponding operation based on the operator (c) is applied to op1 and op2.

3. The switch statement is used to determine the specific operation to perform based on the operator. Each case corresponds to one of the supported operators: '+' for addition, '-' for subtraction, '*' for multiplication, and '/' for division.

4. Depending on the operator, the operation is performed using the values of op1 and op2, and the result is computed.

5. The computed result is then pushed back onto the operands stack using operands.push(result). This allows the result to be available for future calculations or as an operand for subsequent operations.

6. The evaluation continues until all characters in the postfix expression have been processed.

  return operands.top();

In the evaluatePostfixExpression function, the line return operands.top(); is the final step of the evaluation process. It returns the top element of the operands stack, which represents the final result of the postfix expression.

int main() {
    string postfixExpression = "43+5*"; // Example postfix expression
    double result = evaluatePostfixExpression(postfixExpression); // Evaluate the postfix expression
    cout << "Postfix Expression: " << postfixExpression << endl; // Print the postfix expression
    cout << "Result: " << result << endl; // Print the result

    return 0;
}

1. string postfixExpression = "43+5*";: This line initializes a string variable postfixExpression with the example postfix expression "43+5*". You can replace this expression with any valid postfix expression you want to evaluate.

2. double result = evaluatePostfixExpression(postfixExpression); This line calls the evaluatePostfixExpression function and passes the postfixExpression as an argument. The function evaluates the postfix expression and returns the result, which is stored in the result variable of type double.

3. cout << "Postfix Expression: " << postfixExpression << endl; This line prints the original postfix expression before the evaluation. It provides a visual confirmation of the expression that was evaluated.

4. cout << "Result: " << result << endl; This line prints the result of the evaluated postfix expression. It displays the computed value after performing the operations defined in the postfix expression.

5. return 0; This line ends the main function and returns a value of 0 to indicate successful program execution.

Conclusion

the provided code implements a postfix expression evaluator using a stack data structure. It effectively evaluates postfix expressions by iterating over each character and performing the corresponding operations based on the type of character encountered. The code showcases the usage of stacks to store operands during the evaluation process and demonstrates the power and versatility of stack data structures in solving postfix expression problems.