Member Avatar for zhinokin

hi to everyone...

i will make a program about parenthesis checking and my prof said that we will not be using a stack for this.

will you kindly help me to this..

aside from stack can you help me on what to use.?.

  • 2 Contributors
  • 3 Replies
  • 108 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by Salem

Dani AI

Generated

As pointed out, for a single pair of parentheses ( and ) you do not need a stack. The simple rule is: scan left to right, keep an integer balance, increase it for (, decrease it for ). If balance ever goes negative you have an unmatched closing parenthesis; at the end balance must be zero to be balanced. That gives O(n) time and O(1) extra space.

A clear, readable C function (not the compact one-liner shown earlier) looks like this:

int is_balanced(const char *s) {
    int balance = 0;
    for (const char *p = s; *p; ++p) {
        if (*p == '(') {
            ++balance;
        } else if (*p == ')') {
            if (balance == 0) return 0; /* unmatched closing */
            --balance;
        }
    }
    return balance == 0;
}

Quick tests to try while debugging: "" (balanced), "()" (balanced), ")(" (not), "(())" (balanced), "(()" (not). If a check fails, print the index and the running balance to see where the mismatch happens. Also ignore other characters unless the assignment says to validate a full expression.

Important limitation: counters work only when there is a single bracket type and nesting order is not mixed. If the task requires matching multiple types (for example (), [], {}) and ensuring correct nesting order, simple per-type counters are insufficient—the order must be remembered, which requires a stack-like memory (explicit stack, recursion, or equivalent). For formal context and alternative explanations see Dyck language and an algorithm overview at GeeksforGeeks.

Recommended Answers

All 3 Replies

Member Avatar for zhinokin

So use a counter.

should i still use an array for this....?..

Member Avatar for Salem 
counter += 1*(ch=='(') - 1*(ch==')');

It's cryptic because anything simple is the whole answer on a plate.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.