# Prefix Expression Calculator: Polish Notation Evaluation ## Introduction Prefix notation places operators before operands, enabling parenthesis-free expressions. This implementation evaluates prefix expressions using stack operations with O(n) complexity. ### Key Differences from Postfix - Right-to-left evaluation - Operators precede operands - No operator precedence needed ## Core Evaluation Algorithm ```cpp\n#include <stack> #include <cmath> float evaluatePrefix(const std::string& expr) { std::stack<float> stack; // Process right-to-left for (int i = expr.length() - 1; i >= 0; i--) { if (isspace(expr[i])) continue; if (isdigit(expr[i])) { float num = 0, factor = 1; while (i >= 0 && isdigit(expr[i])) { num += (expr[i--]- '0') * factor; factor *= 10; } i++; // Adjust index stack.push(num); } else { // Operator float left = stack.top(); stack.pop(); float right = 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``` ### Evaluation Workflow 1. Parse tokens right-to-left 2. Push operands to stack 3. When operator encountered: - Pop top two operands - Apply operator (left operand OP right operand) - Push result back 4. Final stack value = result ### Advantages - No precedence rules needed - Simplified parsing - Efficient for right-associative operations ## Applications - LISP programming language - Compiler design - Mathematical expression parsers - Functional programming ### Comparison: Prefix vs Postfix | Feature | Prefix | Postfix | |---------|--------|---------| | Evaluation | Right-left | Left-right | | Operator Position | Before operands | After operands | | Parentheses | Not required | Not required | | Human Readability | Lower | Moderate |