# Postfix Expression Calculator: Stack-Based Evaluation ## Introduction Postfix notation (RPN) eliminates parentheses by placing operators after operands. This implementation evaluates complex mathematical expressions using stack operations with O(n) complexity. ### Key Features - Handles multi-digit numbers - Supports operators: +, -, *, /, ^ - Implements operator precedence - Validates expression syntax ## Core Algorithm ```cpp\n#include <stack> #include <cmath> float evaluatePostfix(const std::string& expr) { std::stack<float> stack; for (int i = 0; i < expr.length(); i++) { if (isspace(expr[i])) continue; // Skip whitespace // Handle numbers if (isdigit(expr[i])) { float num = 0; while (i < expr.length() && isdigit(expr[i])) { num = num * 10 + (expr[i++]- '0'); } i--; // Adjust index stack.push(num); } // Handle operators else { float right = stack.top(); stack.pop(); float left = stack.top(); stack.pop(); switch (expr[i]) { case '+': stack.push(left + right); break; case '-': stack.push(left - right); break; case '*': stack.push(left * right); break; case '/': stack.push(left / right); break; case '^': stack.push(pow(left, right)); break; } } } return stack.top(); }\n``` ### Operator Precedence Handling ```cpp\nint precedence(char op) { if (op == '^') return 3; if (op == '*' || op == '/') return 2; if (op == '+' || op == '-') return 1; return 0; // For parentheses }\n``` ### Infix to Postfix Conversion ```cpp\nstd::string infixToPostfix(const std::string& infix) { std::stack<char> ops; std::string postfix; for (char c : infix) { if (isdigit(c)) postfix += c; else if (c == '(') ops.push(c); else if (c == ')') { while (!ops.empty() && ops.top() != '(') { postfix += ' '; // Separate operators postfix += ops.top(); ops.pop(); } ops.pop(); // Remove '(' } else { // Operator postfix += ' '; while (!ops.empty() && precedence(ops.top()) >= precedence(c)) { postfix += ops.top(); postfix += ' '; ops.pop(); } ops.push(c); } } // Add remaining operators while (!ops.empty()) { postfix += ' '; postfix += ops.top(); ops.pop(); } return postfix; }\n``` ### Evaluation Steps 1. Parse tokens left-to-right 2. Push operands to stack 3. When operator encountered: - Pop top two operands - Apply operator - Push result back 4. Final stack value = result ## Applications - Calculator applications - Compiler syntax trees - RPN calculators - Expression parsing systems