Q5

[jwjiawei]

Source

(Semester 1: AY2021/2022)

Description

hi, does anyone have the code for this question? thank u!

Screenshots (if any):

Insert Images here if necessary

[weiming21]

Hi this is my attempt. (a)

class Stack<T> {
    private final List<T> list;

    Stack() {
        this.list = new ArrayList<T>();
    }

    private Stack(List<T> oldList) {
        this.list = new ArrayList<T>(oldList);
    }

    Stack<T> push(T elem) {
        Stack<T> newStack = new Stack<T>(this.list); 
        newStack.list.add(0, elem);
        return newStack;
    }

    boolean isEmpty() {
        return this.list.isEmpty();
    }

    public String toString() { 
        return "Top -> " + this.list;
    }

    Pair<Optional<T>, Stack<T>> pop() {
        Stack<T> newStack = new Stack<T>(this.list);
        Optional<T> opt = this.isEmpty() ? Optional.empty(): Optional.ofNullable(newStack.list.remove(0));
        return new Pair<Optional<T>, Stack<T>>(opt, newStack);
    }
}

(b)

int evaluate(String expr) {
    Scanner sc = new Scanner(expr);
    Stack<Integer> stack = new Stack<>();
    while(sc.hasNext()) {
        String term = sc.next();

        if (term.equals("+") || term.equals("*")) {
            int a = stack.pop().first().orElseThrow();
            int b = stack.pop().second().pop().first().orElseThrow();
            stack = stack.pop().second().pop().second();
            stack = term.equals("+") ? stack.push(a + b) : stack.push(a * b); 
        } else {
            Integer value = Integer.parseInt(term);
            stack = stack.push(value);
        }
    }
    return stack.pop().first().orElseThrow();
}

CMIIW thanks! As for the asynchronous computation aspect in (b), I believe it will not be tested tomorrow

[aldrichwilliams23]

Hey! I'm only able to solve the pop() method but my implementation looks something like this

public Pair<Optional, Stack> pop() { List list = new ArrayList(this.list); Optional elem = Optional.of(list.remove(0)); return new Pair<Optional, Stack>(elem, new Stack(list)); }

[sushiphie]

Hello! Here is my attempt, not sure if its correct though. Think part (b) isn't very efficient though. Hope it helps :-)

(a)

Pair<Optional<T>,Stack<T>> pop() {

    Optional<T> firstItem = Optional.empty();

    Stack<T> newStack = new Stack<T>(this.list);
    if (newStack.list.size() != 0) {
        firstItem = Optional.of(newStack.list.get(0));
        newStack.list.remove(0);
    } 

    return new Pair<Optional<T>, Stack<T>>(firstItem, newStack);
}

(b)

int evaluate(String expr) {
    Scanner sc = new Scanner(expr);
    Stack<Integer> firstStack = new Stack<Integer>();

    while (sc.hasNext()) {
        String term = sc.next();

        if (term.equals("+") {
        int sum = 0; 
                while (!firstStack.isEmpty()) {
            firstTerm = firstStack.pop().first().orElse(0);
            sum += firstTerm;
        }
        firstStack.push(sum);

    } else if (term.equals("*")) {
        int prod = 1; 
        while (!firstStack.isEmpty()) {
            firstTerm = firstStack.pop().first().orElse(0);
            prod *= firstTerm;
        }

        firstStack.push(prod);
        } else {
            Integer value = Integer.parseInt(term);
            firstStack.push(term);
        }

    }

    if (firstStack.isEmpty()) {
    return 0;
    }    
    return firstStack.pop();
}