package postfixeval;
import java.io.*;

// Integer stack for storing intermediate operand values
class OperandStack {
    int size;
    int item[];
    int top;

    public OperandStack() {
        size = 100;
        item = new int[size];
        top = -1;  // -1 means the stack is empty
    }

    // Pushes a value onto the stack
    public void push(int element) {
        if (top == (size - 1)) {
            System.out.println("Stack Overflow");
        } else {
            top++;
            item[top] = element;
        }
    }

    // Pops and returns the top value
    public int pop() {
        if (top == -1) {
            System.out.println("Stack is empty - cannot pop");
            return -1;
        } else {
            int value = item[top];
            top--;
            return value;
        }
    }

    // Returns the top value without removing it
    public int peek() {
        if (top == -1) {
            System.out.println("Stack is empty - cannot peek");
            return -1;
        } else {
            return item[top];
        }
    }
}

// Evaluates a postfix (Reverse Polish Notation) expression
class PostfixExpressionEvaluator {
    OperandStack stack = new OperandStack();
    String postfixExpression;

    public PostfixExpressionEvaluator(String expression) {
        postfixExpression = expression;
    }

    // Returns true if the character is a single-digit operand
    public boolean isOperand(char ch) {
        return (ch >= '0' && ch <= '9');
    }

    // Scans the postfix expression and returns its evaluated integer result
    public int evaluate() {
        char[] characters = postfixExpression.toCharArray();
        int index = 0;
        int rightOperand, leftOperand;

        while (index < characters.length) {
            if (isOperand(characters[index])) {
                // Convert character digit to its integer value and push
                stack.push(characters[index] - '0');
            } else {
                // Pop two operands: rightOperand was pushed last (is on top)
                rightOperand = stack.pop();
                leftOperand  = stack.pop();

                switch (characters[index]) {
                    case '+':
                        stack.push(rightOperand + leftOperand);
                        break;
                    case '-':
                        stack.push(leftOperand - rightOperand);  // order matters
                        break;
                    case '*':
                        stack.push(rightOperand * leftOperand);
                        break;
                    case '/':
                        stack.push(leftOperand / rightOperand);  // order matters
                        break;
                    case '%':
                        stack.push(leftOperand % rightOperand);
                        break;
                }
            }
            index++;
        }
        return stack.pop();  // Final result is the only value left on stack
    }
}

public class PostfixEvaluatorMain {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter postfix expression:");
        String expression = reader.readLine();
        PostfixExpressionEvaluator evaluator = new PostfixExpressionEvaluator(expression);
        System.out.println("Result: " + evaluator.evaluate());
    }
}