balanced-groupers-pda.cpp

#include <stack>
#include <map>
#include <vector>
#include <iostream>
#include <cstdint>

using symbol = char;
using state = std::uint32_t;
using symbol_state_pair = std::pair<symbol, state>;
using transition_map = std::map<symbol_state_pair, std::vector<state>>;

class pda {
public:
	pda(const state start_state, const transition_map& transitions)
		: start_state{start_state}, transitions{transitions} {}

	bool accept(const std::string& input) {
		decltype(s){}.swap(s);
		s.push(start_state);

		for (const auto sym : input) {
			if (s.empty()) return false;

			const auto it = transitions.find({ sym, s.top() });

			if (it == std::end(transitions)) return false;

			s.pop();

			for (auto jt = it->second.rbegin(); jt != it->second.rend(); ++jt)
				s.push(*jt);
		}

		return s.empty() || s.top() == start_state;
	}

private:
	state start_state;
	transition_map transitions;
	std::stack<state> s;
};

int main(int argc, char** argv) {
	if (argc < 2) return -1;

	// A -> (BA | {CA | [DA | <EA
	// B -> ) | (BB | {CB | [DB | <EB
	// C -> } | {CC | (BC | [DC | <EC
	// D -> ] | [DD | (BD | {CD | <ED
	// E -> > | <EE | (BE | {CE | [DE

	const state A = 256;
	const state B = 257;
	const state C = 258;
	const state D = 259;
	const state E = 260;

	pda automata{A, {
		{ { '(', A }, { B, A } },
		{ { '{', A }, { C, A } },
		{ { '[', A }, { D, A } },
		{ { '<', A }, { E, A } },
		{ { ')', B }, { } },
		{ { '(', B }, { B, B } },
		{ { '{', B }, { C, B } },
		{ { '[', B }, { D, B } },
		{ { '<', B }, { E, B } },
		{ { '}', C }, { } },
		{ { '{', C }, { C, C } },
		{ { '(', C }, { B, C } },
		{ { '[', C }, { D, C } },
		{ { '<', C }, { E, C } },
		{ { ']', D }, { } },
		{ { '[', D }, { D, D } },
		{ { '(', D }, { B, D } },
		{ { '{', D }, { C, D } },
		{ { '<', D }, { E, D } },
		{ { '>', E }, { } },
		{ { '<', E }, { E, E } },
		{ { '(', E }, { B, E } },
		{ { '{', E }, { C, E } },
		{ { '[', E }, { D, E } },
	}};

	for (auto i = 1; i < argc; ++i) {
		std::cout << argv[i] << " => " << std::boolalpha << automata.accept(argv[i]) << std::endl;
	}
}