Discussion on: Verify matching parens, brackets and braces with Elixir

[Alim Nastaev]

If we have 2 inputs:

1. {({})} and 2. { ( { } ) }

In 1 we have to perform 6 iterations to walk through it and in 2 it's 11, right?

So is there a way we can walk through both inputs with the same amount of iterations? If yes - we can apply the same approach to our solution.

(Pattern matching is whispering here something for us again 🙂 )

[Lucas Perez]

Well, if we could group the whitespaces together during the match, that would be great. The program would just have to check non-whitespace characters.
Something like this would work for only a single space

defp run_check("{ " <> rest, [stack, result]), do: run_check(rest, ["{" <> stack, result])

And then repeat for brackets and parenthesis.

It would be perfect to match an unspecified amount of whitecharacters at once. Using a regex it would be a breeze, but I'm sure that is not what we want here.

In fact, we would like to match everything that is not one of { [ ( ) ] }, with unspecified length, not just whitespaces. Then we could ignore everything that is irrelevant, essentially doing a filter inside the match.
After achieving a way to do that, parsing abc {} would require the same amount of iterations as {}.

But how do I do it?
Matches like "{" <> irrelevant <> "{" fail because the size of the variable irrelevant is unknown, and "{" <> <<irr::binary>> <> "{" fails because a binary field without a size is only allowed as the last member of the match (basically the same problem, Elixir doesn't know up to what point to check).

I could write like 200 headers of the function for one, two, three, ..., 200 character length for the irrelevant variable, but that would be tedious. I am 100% sure there is a way to make Elixir itself write some Elixir code for me, maybe use some range to dynamically create these functions, and leave a last header matching whatever didn't match before. It would speed up the parsing for most cases, and in the worst scenario it would be the same as it is now.

[Alim Nastaev]

I cleaned up/refactored my solution. Check it out down below.

There is a section ### making a recursive step wider ### - that code explains my thoughts. I left some logs in that part, so if you run code from iex you will clearly see what I was trying to say and the output looks like this:

iex::8> ParensBracketsBraces.matching?("(a + [ b - c ] )")

ELEMENT <> WHITESPACE 

: [elem: "a", input_tail: "+ [ b - c ] )", stack: "("]

ELEMENT <> WHITESPACE 

: [elem: "+", input_tail: "[ b - c ] )", stack: "("]

WHITESPACE <> ELEMENT 

: [elem: "b", input_tail: " - c ] )", stack: "[("]

WHITESPACE <> ELEMENT 

: [elem: "-", input_tail: " c ] )", stack: "[("]

WHITESPACE <> ELEMENT 

: [elem: "c", input_tail: " ] )", stack: "[("]

BTW, hope you use iex - very powerful tool...

defmodule ParensBracketsBraces do
  @openers ["{", "[", "("]
  @closers ["}", "]", ")"]
  @all @openers ++ @closers

  def matching?(input) when is_binary(input), do: run_check("", input)
  def matching?(input), do: "#{inspect(input)} is not a valid string."
  def matching?(), do: "input should be a valid string"

  ### --- BASE CASES --- ###
  # matching pairs
  defp run_check("" = _stack, "" = _input), do: true
  # no matches
  defp run_check(_, "" = _input), do: false

  ### matches on opener only and putting it to the stack ###
  defp run_check(stack, <<opener::binary-size(1)>> <> input_tail)
       when opener in @openers,
       do: run_check(opener <> stack, input_tail)

  ### covering case where there are only closers ###
  defp run_check("", <<closer::binary-size(1)>> <> _tail_input)
       when closer in @closers,
       do: false

  ### comparing top item in the stack with closer ###

  defp run_check("[" <> stack_tail, "]" <> input_tail),
    do: run_check(stack_tail, input_tail)

  defp run_check("(" <> stack_tail, ")" <> input_tail),
    do: run_check(stack_tail, input_tail)

  defp run_check("{" <> stack_tail, "}" <> input_tail),
    do: run_check(stack_tail, input_tail)

  ###############################

  ### making a recursive step wider ###

  defp run_check(stack, <<elem::binary-size(1)>> <> " " <> input_tail)
       when elem not in @all do
    IO.inspect(binding(), label: "\nELEMENT <> WHITESPACE \n\n")
    run_check(stack, input_tail)
  end

  defp run_check(stack, " " <> <<elem::binary-size(1)>> <> input_tail)
       when elem not in @all do
    IO.inspect(binding(), label: "\nWHITESPACE <> ELEMENT \n\n")
    run_check(stack, input_tail)
  end

  ###############################

  ### if not openers or/and closers ###
  defp run_check(stack, <<_::binary-size(1)>> <> input_tail), do: run_check(stack, input_tail)
end