Generic Stack Class

Lab Java Advanced 30 points

Implement class Stack<T> backed by an ArrayList, with push, pop (throws RuntimeException("empty")), peek and size. Use a Stack<Integer> to evaluate a postfix (RPN) expression like 3 4 + 2 *.

Input

One line: a postfix expression with + - * /.

Output

The result (integer division), or error.

Example

Input

3 4 + 2 *

Output

Sample input available Sample output available

Editor

Java

Hints

Numbers are pushed; an operator pops two numbers and pushes the result.

Pop order matters: the second pop is the left operand.

Solution explanation

Postfix needs no parentheses - a stack evaluates it in one left-to-right pass.

Show solution

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Stack<T> {
    private final List<T> items = new ArrayList<T>();

    void push(T item) {
        items.add(item);
    }

    T pop() {
        if (items.isEmpty()) {
            throw new RuntimeException("empty");
        }
        return items.remove(items.size() - 1);
    }

    T peek() {
        return items.get(items.size() - 1);
    }

    int size() {
        return items.size();
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Stack<Integer> stack = new Stack<Integer>();
        try {
            for (String t : sc.nextLine().trim().split("\\s+")) {
                if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) {
                    int b = stack.pop(), a = stack.pop();
                    int r = t.equals("+") ? a + b : t.equals("-") ? a - b : t.equals("*") ? a * b : a / b;
                    stack.push(r);
                } else {
                    stack.push(Integer.parseInt(t));
                }
            }
            System.out.println(stack.size() == 1 ? String.valueOf(stack.pop()) : "error");
        } catch (RuntimeException e) {
            System.out.println("error");
        }
    }
}

Output

Answer