A stack is a data structure that follows the Last In First Out (LIFO) principle. It is a type of linear list where insertions and deletions are restricted to one end, known as the top. The opposite end is referred to as the bottom.

Push and Pop Operations

Push refers to adding an element to the top of the stack, while pop removes the topmost element from the stack.

Use Cases for Stacks

• Subroutine Calls: Before jumping to a subroutine, the next instruction's address is stored in the stack, allowing the program to return to the correct location after the subroutine completes.
• Handling Recursion: Similar to subroutine calls but also includes storing parameters and local variables.
• Expression Conversion: Converting infix expressions to postfix (Reverse Polish Notation) and evaluating them.
• Binary Tree Traversal.
• Depth-First Search (DFS) for graphs.

Implementing a Calculator Using Stacks (Infix Expressions)

package com.example.stack;

public class Calculator {
    public static void main(String[] args) {
        String expression = "70+2*6-4";
        ArrayStack numStack = new ArrayStack(10);
        ArrayStack operStack = new ArrayStack(10);

        int index = 0;
        char ch;
        String numberBuffer = "";

        while (index < expression.length()) {
            ch = expression.charAt(index);

            if (operStack.isOperator(ch)) {
                while (!operStack.isEmpty() && 
                      operStack.getPriority(ch) <= operStack.getPriority(operStack.peek())) {
                    int num2 = numStack.pop();
                    int num1 = numStack.pop();
                    int op = operStack.pop();
                    numStack.push(numStack.compute(num1, num2, op));
                }
                operStack.push(ch);
            } else {
                numberBuffer += ch;
                if (index == expression.length() - 1 || operStack.isOperator(expression.charAt(index + 1))) {
                    numStack.push(Integer.parseInt(numberBuffer));
                    numberBuffer = "";
                }
            }
            index++;
        }

        while (!operStack.isEmpty()) {
            int num2 = numStack.pop();
            int num1 = numStack.pop();
            int op = operStack.pop();
            numStack.push(numStack.compute(num1, num2, op));
        }

        System.out.printf("Expression %s = %d\n", expression, numStack.pop());
    }
}

class ArrayStack {
    private int maxSize;
    private int[] stackArray;
    private int top = -1;

    public ArrayStack(int size) {
        this.maxSize = size;
        stackArray = new int[size];
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public void push(int value) {
        if (!isFull()) {
            stackArray[++top] = value;
        }
    }

    public int pop() {
        if (!isEmpty()) {
            return stackArray[top--];
        }
        throw new RuntimeException("Stack underflow");
    }

    public int peek() {
        return stackArray[top];
    }

    public int getPriority(char operator) {
        if (operator == '*' || operator == '/') return 2;
        if (operator == '+' || operator == '-') return 1;
        return -1;
    }

    public boolean isOperator(char c) {
        return "+-*/".indexOf(c) != -1;
    }

    public int compute(int left, int right, int operator) {
        switch (operator) {
            case '+': return left + right;
            case '-': return left - right;
            case '*': return left * right;
            case '/': return left / right;
            default: throw new IllegalArgumentException("Invalid operator");
        }
    }
}

Prefix Expressions

Prefix expressions, also called Polish notation, place operators before operands. For example, the prefix expression for (3 + 4) * 5 - 6 is - * + 3 4 5 6.

Evaluating Prefix Expressions

To evaluate prefix expressions, scan from right to left:

• Push numbers onto a stack.
• When encountering an operator, pop two values, apply the operation, and push the result back onto the stack.

Infix Expressions

Infix expression are standard arithmetic expressions like (3 + 4) * 5 - 6. While familiar to humans, they can be complex for computers to evaluate directly, often requiring conversion to postfix form.

Postfix Expressions

Postfix expressions, or Reverse Polish Notation, place operators after operends. For example, the postfix epxression for (3 + 4) * 5 - 6 is 3 4 + 5 * 6 -.

Evaluating Postfix Expressions

To evaluate postfix expressions, scan from left to right:

• Push numbers onto a stack.
• When encountering an operator, pop two values, apply the operation, and push the result back onto the stack.

package com.example.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PostfixEvaluator {
    public static void main(String[] args) {
        String postfix = "3 4 + 5 * 6 -";
        List<String> tokens = tokenize(postfix);
        int result = evaluate(tokens);
        System.out.println("Result: " + result);
    }

    private static List<String> tokenize(String expr) {
        String[] parts = expr.split(" ");
        return new ArrayList<>(List.of(parts));
    }

    private static int evaluate(List<String> tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(applyOperation(a, b, token));
            }
        }
        return stack.pop();
    }

    private static boolean isNumber(String token) {
        try {
            Integer.parseInt(token);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }

    private static int applyOperation(int a, int b, String op) {
        switch (op) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;
            default: throw new IllegalArgumentException("Unknown operator: " + op);
        }
    }
}

Converting Infix to Postfix

1. Initialize two stacks: one for operators (s1) and one for output (s2).
2. Scan the infix expression from left to right.
3. Push numbers directly to s2.
4. Handle operators based on precedence and associativity.
5. Manage parentheses by pushing them to s1 and resolving when encountering closing ones.
6. After processing, transfer remaining operators from s1 to s2.
7. Reverse s2 to obtain the postfix expression.

package com.example.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InfixToPostfix {
    public static void main(String[] args) {
        String infix = "1+((2+3)*4)-5";
        List<String> tokens = tokenize(infix);
        List<String> postfix = convertToPostfix(tokens);
        System.out.println("Postfix: " + postfix);
    }

    private static List<String> tokenize(String expr) {
        List<String> tokens = new ArrayList<>();
        StringBuilder buffer = new StringBuilder();
        for (char c : expr.toCharArray()) {
            if (Character.isDigit(c)) {
                buffer.append(c);
            } else {
                if (buffer.length() > 0) {
                    tokens.add(buffer.toString());
                    buffer.setLength(0);
                }
                tokens.add(Character.toString(c));
            }
        }
        if (buffer.length() > 0) {
            tokens.add(buffer.toString());
        }
        return tokens;
    }

    private static List<String> convertToPostfix(List<String> tokens) {
        Stack<String> operators = new Stack<>();
        List<String> output = new ArrayList<>();

        for (String token : tokens) {
            if (isNumber(token)) {
                output.add(token);
            } else if ("(".equals(token)) {
                operators.push(token);
            } else if (")".equals(token)) {
                while (!"(".equals(operators.peek())) {
                    output.add(operators.pop());
                }
                operators.pop(); // Remove '('
            } else {
                while (!operators.isEmpty() && precedence(token) <= precedence(operators.peek())) {
                    output.add(operators.pop());
                }
                operators.push(token);
            }
        }

        while (!operators.isEmpty()) {
            output.add(operators.pop());
        }

        return output;
    }

    private static boolean isNumber(String token) {
        return token.chars().allMatch(Character::isDigit);
    }

    private static int precedence(String op) {
        if ("+".equals(op) || "-".equals(op)) return 1;
        if ("*".equals(op) || "/".equals(op)) return 2;
        return 0;
    }
}