Avatar of shmibs

shmibs's solution

to Bracket Push in the C Track

Published at Nov 13 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution was written.

Given a string containing brackets [], braces {}, parentheses (), or any combination thereof, verify that any and all pairs are matched and nested correctly.

Getting Started

Make sure you have read the "Guides" section of the C track on the Exercism site. This covers the basic information on setting up the development environment expected by the exercises.

Passing the Tests

Get the first test compiling, linking and passing by following the three rules of test-driven development.

The included makefile can be used to create and run the tests using the test task.

make test

Create just the functions you need to satisfy any compiler errors and get the test to fail. Then write just enough code to get the test to pass. Once you've done that, move onto the next test.

As you progress through the tests, take the time to refactor your implementation for readability and expressiveness and then go on to the next test.

Try to use standard C99 facilities in preference to writing your own low-level algorithms or facilities by hand.

Source

Ginna Baker

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

test_bracket_push.c

#include "vendor/unity.h"
#include "../src/bracket_push.h"
#include <stdbool.h>

void setUp(void)
{
}

void tearDown(void)
{
}

void test_paired_square_brackets(void)
{
   const char *input = "[]";
   TEST_ASSERT_TRUE(is_paired(input));
}

void test_empty_string(void)
{
   TEST_IGNORE();               // delete this line to run test
   const char *input = "";
   TEST_ASSERT_TRUE(is_paired(input));
}

void test_unpaired_brackets(void)
{
   TEST_IGNORE();
   const char *input = "[[";
   TEST_ASSERT_FALSE(is_paired(input));
}

void test_wrong_ordered_brackets(void)
{
   TEST_IGNORE();
   const char *input = "}{";
   TEST_ASSERT_FALSE(is_paired(input));
}

void test_wrong_closing_bracket(void)
{
   TEST_IGNORE();
   const char *input = "{]";
   TEST_ASSERT_FALSE(is_paired(input));
}

void test_paired_with_whitespace(void)
{
   TEST_IGNORE();
   const char *input = "{ }";
   TEST_ASSERT_TRUE(is_paired(input));
}

void test_simple_nested_brackets(void)
{
   TEST_IGNORE();
   const char *input = "{[]}";
   TEST_ASSERT_TRUE(is_paired(input));
}

void test_several_paired_brackets(void)
{
   TEST_IGNORE();
   const char *input = "{}[]";
   TEST_ASSERT_TRUE(is_paired(input));
}

void test_paired_and_nested_brackets(void)
{
   TEST_IGNORE();
   const char *input = "([{}({}[])])";
   TEST_ASSERT_TRUE(is_paired(input));
}

void test_unopened_closing_brackets(void)
{
   TEST_IGNORE();
   const char *input = "{[)][]}";
   TEST_ASSERT_FALSE(is_paired(input));
}

void test_unpaired_and_nested_brackets(void)
{
   TEST_IGNORE();
   const char *input = "([{])";
   TEST_ASSERT_FALSE(is_paired(input));
}

void test_paired_and_wrong_nested_brackets(void)
{
   TEST_IGNORE();
   const char *input = "[({]})";
   TEST_ASSERT_FALSE(is_paired(input));
}

void test_math_expression(void)
{
   TEST_IGNORE();
   const char *input = "(((185 + 223.85) * 15) - 543)/2";
   TEST_ASSERT_TRUE(is_paired(input));
}

void test_complex_latex_expression(void)
{
   TEST_IGNORE();
   const char *input =
       "\\left(\\begin{array}{cc} \\frac{1}{3} & x\\\\ \\mathrm{e}^{x} &... x^2 \\end{array}\\right)";
   TEST_ASSERT_TRUE(is_paired(input));
}

int main(void)
{
   UnityBegin("test/test_bracket_push.c");

   RUN_TEST(test_paired_square_brackets);
   RUN_TEST(test_empty_string);
   RUN_TEST(test_unpaired_brackets);
   RUN_TEST(test_wrong_ordered_brackets);
   RUN_TEST(test_wrong_closing_bracket);
   RUN_TEST(test_paired_with_whitespace);
   RUN_TEST(test_simple_nested_brackets);
   RUN_TEST(test_several_paired_brackets);
   RUN_TEST(test_paired_and_nested_brackets);
   RUN_TEST(test_unopened_closing_brackets);
   RUN_TEST(test_unpaired_and_nested_brackets);
   RUN_TEST(test_paired_and_wrong_nested_brackets);
   RUN_TEST(test_math_expression);
   RUN_TEST(test_complex_latex_expression);

   UnityEnd();
   return 0;
}
#include <string.h>
#include <stdint.h>
#include <stdbool.h>

#include "bracket_push.h"

/* the uint8_t index of sp into a stack */
#define SP2IDX(sp) ((sp) / 4)
/* the offset (in 2-bit intervals) of sp into that uint8_t */
#define SP2OFF(sp) (((sp) % 4) * 2)
/* a mask of only the bits at that offset */
#define SP2MASK(sp) (0x03 << SP2OFF(sp))

static inline void set_at(uint8_t b, uint8_t sp, uint8_t *stack)
{
	b <<= SP2OFF(sp);
	stack[SP2IDX(sp)] = (stack[SP2IDX(sp)] & ~SP2MASK(sp)) | b;
}

static inline bool test_at(uint8_t b, uint8_t sp, uint8_t *stack)
{
	b <<= SP2OFF(sp);
	return (stack[SP2IDX(sp)] & SP2MASK(sp)) == b;
}

bool is_paired(const char *s)
{
	uint8_t stack[32] = {0};
	uint8_t sp = 0;
	/* each char uses two bits, so can have a max-nesting-depth of 128 */
	const uint8_t max_depth = 4 * (sizeof(stack)/sizeof(uint8_t));

	uint32_t i;
	uint8_t type;

	/* return type should really be something that can indicate errors,
	 * but ┐(¯-¯)┌ */
	if (s == NULL)
		return false;

	for (i = 0; s[i] != '\0'; i++) {
		if (i == UINT32_MAX)
			return false;

		/* type will be 0x01 for prens, 0x02 for brackets, 0x03 for curlies.
		 * the fall-through comments are necessary to make gcc shut up */
		type = 0x01;
		switch (s[i]) {

		case '{': type++; // fall-through
		case '[': type++; // fall-through
		case '(':
			/* too much nesting :c */
			if (sp >= max_depth)
				return false;

			set_at(type, sp, stack);
			sp++;
			break;

		case '}': type++; // fall-through
		case ']': type++; // fall-through
		case ')':
			/* underflow :c */
			if(sp == 0)
				return false;

			if (!test_at(type, sp-1, stack))
				return false;

			sp--;
		}
	}

	if (sp != 0)
		return false;

	return true;
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?