-5

I have often found this weird while using Stacks in C++ and I'm not sure what the exact root of the problem is. It would be better explained with a snippet of the code: (I am trying to get the minimum value of a stack and pushing/popping etc. as usual)

class MinStack {
private:
    stack<int> ans;
    stack<int> min_collector;

public:
    void push(int x) {
        ans.push(x);
        if (min_collector.empty() || getMin()>=x) {
            min_collector.push(x);
        }
    }

    void pop() {
        if (ans.top()==getMin()) {
            min_collector.pop();
        }
        ans.pop();
    }

    int top() {
        return ans.top();
    }

    int getMin() {
        return min_collector.top();
    }

};

The above code works fine. However, in the push(int x) function, if I edit the "if" condition like this:

(getMin()>=x  || min_collector.empty())

I get a runtime error, has anyone else faced this issue? Why should the order in a "or" condition matter?

Manas Shukla
  • 15
  • 4
  • 3
    What do you think happens on `min_collector.top()` when the stack is empty? – tkausl Dec 08 '17 at 17:07
  • 1
    "Why should the order in a "or" condition matter?" because there is short circuit: https://stackoverflow.com/questions/1799072/c-short-circuiting-of-booleans – Slava Dec 08 '17 at 17:09

1 Answers1

2

These conditions are evaluated from left to right, and execution aborts once the first term has returned true.

For logic && execution aborts once the first term has returned false.

You get a runtime error because it is illegal to attempt to access the top() element of a stack when it's empty - there is no top element.

Ext3h
  • 5,713
  • 17
  • 43