Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E3-1'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-1

Question

A common problem for compilers and text editors is determining whether the parentheses in a string are balanced and properly nested. For example, the string ((())())() contains properly nested pairs of parentheses, while the strings )()( and ()) do not. Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. For full credit, identify the position of the first offending parenthesis if the string is not properly nested and balanced.

Solution

C++ code.

#include <cassert>
#include <string>

constexpr char PAREN_OPEN{'('};
constexpr char PAREN_CLOSE{')'};

struct Balance_parenthesis {
    bool balanced;
    int offending_pos;
};

Balance_parenthesis check_bal(std::string_view target) {
    // loop to examine whole charactors
    // if ( exists, counter++
    // if ) exists, counter--
    // if counter < 0, record the position and return the result
    int cnt{0};
    std::size_t sz{target.size()};
    for (int i = 0; i < sz; i++) {
        if (target[i] == PAREN_OPEN) ++cnt;
        if (target[i] == PAREN_CLOSE) --cnt;
        if (cnt < 0) return {false, i};
    }
    return {true, -1};
}

int main(int argc, char const* argv[]) {
    std::string s{"()"};
    assert(check_bal(s).balanced);
    s = "(a)b(c)";
    assert(check_bal(s).balanced);
    s = "((())())()";
    assert(check_bal(s).balanced);
    s = ")()( ";
    auto result{check_bal(s)};
    assert(!result.balanced && result.offending_pos == 0);
    s = "())";
    result = check_bal(s);
    assert(!result.balanced && result.offending_pos == 2);
    s = "std::size_t sz{target.size()};";
    assert(check_bal(s).balanced);
    return 0;
}