Do not use global variables.
Global variables cause an "effect at a distance" which makes reasoning about code difficult.
Instead, variables should have as tight a scope as possible, and the functions to operate on them should take a reference/pointer to those variables.
Separate technical concerns from functional concerns.
The main purpose of a stack is to manage memory & elements. Ideally, it should NOT concern itself with what the elements are, and of course it should certainly not concern itself with why you want a stack.
You have the latter separation (Good!), but not the former as your stack is hardcoded to work with char. A little sprinkling of templates would help make it clearer:
template <typename T>
class Stack {
// TODO
};
Encapsulate the internals of your container.
You should not expose the internals of your container for anyone to peer at them, or possibly worse modify them. The former makes it hard to change the implementation (for features or performance) and the latter makes it hard to maintain invariants.
template <typename T>
class Stack {
public:
// TODO
private:
struct Node {
T element;
Node* next;
};
Node* top = nullptr;
};
Use smart pointers, rather than rolling your own.
Carefully managing memory is hard, and as a result your stack is faulty.
Your restricted usage only results in leaking memory, so far: in the case the stack is not empty, you forget to free it.
However, were you to attempt to copy the stack, your program would likely start crashing because you failed to implement a copy constructor.
You could implement a copy constructor, and all other necessary methods. Or you could reach for the appropriate memory management solution for the problem at hand: in this case std::unique_ptr<T>.
template <typename T>
class Stack {
public:
// TODO
private:
struct Node {
T element;
std::unique_ptr<Node> next;
};
std::unique_ptr<Node> top;
};
Do not abort in case of human error.
Your pop function is concerning; a simple mistake causes the whole program to come down crashing.
You could "simply" add a documentation comment indicating that calling pop on an empty stack will cause the program to crash. It wouldn't be user-friendly, though.
The better solution is to figure how to inform the caller that the stack is empty, and for that std::optional<T> is available.
template <typename T>
class Stack {
public:
/// Attempts to pop the top of the stack.
///
/// Returns the (former) top of the stack, or `nullopt` if the stack was empty.
std::optional<T> pop() {
if (head == nullptr) {
return std::nullopt;
}
auto top = std::exchange(this->top, this->top->next);
return std::move(top->element);
}
private:
// Unchanged.
};
Similarly, peek can be implemented to return T const* (null if the stack is empty). I'll leave that to you.
Demonstrating the isBalanced function
@janos already suggested you use an isBalanced function, and I agree. It would also make it easier to test your code... and tests are badly missing.
In any case, here is such a function:
// Pair-wise matched open and close brackets.
static std::string_view const OPEN = "({[";
static std::string_view const CLOSE = ")}]";
static bool is_open(char c) {
return OPEN.find(c) != std::string_view::npos;
}
static bool is_close(char c) {
return CLOSE.find(c) != std::string_view::npos;
}
static bool is_matching(char open, char close) {
assert(is_open(open));
assert(is_close(close));
return OPEN.find(open) == CLOSE.find(close);
}
/// Returns whether the brackets are balanced within `str`.
///
/// The brackets considered are (), {}, and []. Other characters are
/// skipped.
///
/// Returns false if the brackets are unbalanced, or ill-matched.
bool is_balanced(std::string_view str) {
Stack<char> stack;
for (char c : str) {
if (is_open(c)) {
stack.push(c);
continue;
}
// In a real compiler, non-brackets are skipped.
if (!is_close(c)) {
continue;
}
auto top = stack.pop();
// Too many closing brackets.
if (!top.has_value()) {
return false;
}
// Ill-matched brackets.
if (!is_matching(top.value(), c)) {
return false;
}
}
// Too many opening brackets.
return stack.is_empty();
}
And once again, like @janos, I encourage the use of "guard clauses", that is, if branches that immediately return/continue/break in order to avoid deeply nested statements.
Parting Question
Try pushing a million elements in the stack above, then destroy it (let the variable fall out of scope). Did your code crash? Do you understand what is the cause?
It's a common issue for lists and trees structures, so try and work out a solution ;)
