2
\$\begingroup\$

Problem: Stacks can be used to check whether the given expression has balanced symbols. This algorithm is very useful in compilers. Each time the parser reads one character at a time. If the character is an opening delimiter such as (, {, or [- then it is written to the stack. When a closing delimiter is encountered like),}, or]-the stack is popped. The opening and closing delimiters are then compared. If, the parsing of the string continues. If they do not match, the parser indicates that there is an error on the line.

Create an implementation using stacks. Your output must include the following:

a.Stack using Arrays (I dont have)

b.Stack using Linked Lists (I already have)

Here's my code for linked list:

#include <bits/stdc++.h>
#include <cstdlib>
#include<string>

//Linked list
struct Node{
    char phr;
    Node* next;
    Node (char h){
        phr=h;
        next=NULL;
    }
};

Node* top;

void push(char phr){
  Node* temp=new Node(phr);
  temp->next = top;
  top = temp;
}

bool isEmpty(){
    return top==NULL;
}

char peek(){
  if (!isEmpty())
    return top->phr;
  else
    return true;
}

void pop(){
    Node* temp;
    if (top==NULL){
        std::cout<<"Stack underflow";
        exit(1);
    }
  
    else{
        temp = top;
        top=top->next;
        free (temp);
    }
}

int main(){
    std::string symb = "{[()]}";
    std::string choice;
    std::cout<<"Balanced or Unbalanced" <<std::endl;
    std::cout<<"Enter Expression: ";
    std::cin>>choice;
  
for(int i=0;i<choice.length();i++){
    if (symb.find(choice[i]) != std::string::npos){
    if(isEmpty()){
        push (choice[i]);
       }
    else if (peek()=='('&& choice[i]==')' || peek() =='{'&&choice[i]=='}' ||peek()=='['&&choice[i]==']'){
      pop();
    }
      else{
        push(choice[i]);
      }
    }
}
    
    if (isEmpty()){
      std::cout<<"Balanced Expression";
    }
    
    else{
        std::cout<<"Unbalanced Expression" <<std::endl;
    }
    
    return 0;
}
\$\endgroup\$

3 Answers 3

6
\$\begingroup\$

<bits/stdc++.h> is not a standard header. It's an implementation detail of the compiler you're using, and can be changed or removed without notice. Include the necessary standard headers yourself.

We have std::forward_list we can use, rather than implementing one from scratch.

This looks odd:

char peek(){
  if (!isEmpty())
    return top->phr;
  else
    return true;
}

Why do we return a boolean from a char function? That's utterly meaningless. Prefer to throw an exception, if we test at all. The standard library containers make it the caller's responsibility to ensure we don't peek or pop an empty list, saving overhead in the class.

We have mismatched new with std::free()¹. That's a serious error, and can break your code.


¹ misspelt as simply free() - the same problem exists where std::exit() is meant.

\$\endgroup\$
5
\$\begingroup\$

Stop processing on first unbalanced closing

When an unbalanced closing symbol is found, the program happily continues until the end of the input, even when the answer is already known. Consider for example the cases:

  • A closing symbol is found, but the stack is empty
  • A closing symbol is found that doesn't match the last opening symbol

Create an isBalanced function

The main function does many things:

  • read input
  • check if the input is balanced
  • print output

The logic to check if the input is balanced can be wrapped nicely in a function that takes a string as input and returns a boolean. This will also make it easier to return false early when the input is clearly unbalanced (see the previous point).

Use for-each loop when possible

The main loop uses old-fashioned counting loop, and then the loop body references choice[i] many times. This is repetitive and error-prone.

It would be better to write the loop like this:

for (auto c : choice) {

and then you can write simply c for the current character.

Indent and format the code nicely

Nice indentation for blocks of code helps readers greatly. Also it's recommended to add spaces around operators.

Here's a part of the code nicely indented and formatted following a widely used style:

int main() {
    std::string symb = "{[()]}";
    std::string choice;
    std::cout << "Balanced or Unbalanced" << std::endl;
    std::cout << "Enter Expression: ";
    std::cin >> choice;

    for (int i = 0; i < choice.length(); i++) {
        if (symb.find(choice[i]) != std::string::npos) {
            if (isEmpty()) {
                push (choice[i]);
            } else if (peek() == '(' && choice[i] == ')' || peek() == '{' && choice[i] == '}' || peek() == '[' && choice[i] == ']') {
                pop();
            } else {
                push(choice[i]);
            }
        }
    }
    

Prefer less deeply nested code

The loop skips over characters that are not parentheses:

for(int i=0;i<choice.length();i++){
    if (symb.find(choice[i]) != std::string::npos){
        // the symbol is found!
        // many lines of code
        // ...
    }
}

It would be better to reduce the nesting using continue:

for(int i=0;i<choice.length();i++){
    if (symb.find(choice[i]) == std::string::npos) {
        continue;
    }

    // the symbol is found!
    // many lines of code
    // ...
}
\$\endgroup\$
1
\$\begingroup\$

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 ;)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.