infix-to-postfix.cpp

/*
 * ============================================================================
 * Topic : Infix to postfix + evaluation
 * Level : Data structures — stacks
 * ----------------------------------------------------------------------------
 * What you'll learn
 *   Convert a single-digit infix expression to postfix with an operator stack.
 *   Pop operators while stack precedence ≥ current operator (shunting-yard).
 *   Evaluate the postfix with a second value stack (operands then operators).
 * ----------------------------------------------------------------------------
 * How to run
 *   • OnlineGDB: https://www.onlinegdb.com/online_c++_compiler
 *     Open this file on GitHub → copy → paste into OnlineGDB → C++ → Run
 *   • Codespaces (whole repo): https://codespaces.new/baheesa/cpp-practice?quickstart=1
 *   • Local: g++ -std=c++17 -Wall -o app "03-data-structures/infix-to-postfix.cpp" && ./app
 * ----------------------------------------------------------------------------
 * Example input
 *   3+4*2
 * Example output
 *   Postfix: 342*+
 *   Value:    11
 * ============================================================================
 */

#include <iostream>
#include <string>
#include <cctype>
#include <cmath>
using namespace std;

// Tiny fixed stack for operators (chars). top == -1 means empty.
class CharStack {
    char data[64];
    int top;
public:
    CharStack() : top(-1) {}
    bool empty() const { return top < 0; }
    void push(char c) { data[++top] = c; }
    char pop() { return data[top--]; }
    char peek() const { return data[top]; }
};

class IntStack {
    int data[64];
    int top;
public:
    IntStack() : top(-1) {}
    void push(int v) { data[++top] = v; }
    int pop() { return data[top--]; }
};

// Higher number = binds tighter. Used to decide when to pop.
int precedence(char op) {
    if (op == '^') return 3;
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

bool isOp(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

// Shunting-yard (simplified): digits go straight to output; operators wait on a stack.
string toPostfix(const string& in) {
    CharStack ops;
    string post;
    for (char c : in) {
        if (isdigit(static_cast<unsigned char>(c))) {
            post.push_back(c);  // operand → output immediately
        } else if (isOp(c)) {
            // Pop while top has ≥ precedence so * happens before + in "3+4*2".
            while (!ops.empty() && precedence(ops.peek()) >= precedence(c))
                post.push_back(ops.pop());
            ops.push(c);
        }
    }
    while (!ops.empty())  // flush remaining operators
        post.push_back(ops.pop());
    return post;
}

// Scan postfix left→right: push digits; on an operator, pop two operands and push result.
int evalPostfix(const string& post) {
    IntStack st;
    for (char c : post) {
        if (isdigit(static_cast<unsigned char>(c))) {
            st.push(c - '0');  // char digit → int value
        } else {
            int b = st.pop();  // right operand (was pushed later)
            int a = st.pop();  // left operand
            int r = 0;
            if (c == '+') r = a + b;
            else if (c == '-') r = a - b;
            else if (c == '*') r = a * b;
            else if (c == '/') r = a / b;
            else if (c == '^') r = static_cast<int>(pow(a, b));
            st.push(r);
        }
    }
    return st.pop();  // final value left on the stack
}

int main() {
    string expr;
    cout << "Infix (single digits, no spaces, e.g. 3+4*2): ";
    cin >> expr;

    string post = toPostfix(expr);
    cout << "Postfix: " << post << '\n';
    cout << "Value:    " << evalPostfix(post) << '\n';
    return 0;
}