# LeetCode 20. Valid Parentheses (LaTeX)

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

## Example

Example 1:

Input: "()"
Output: true


Example 2:

Input: "()[]{}"
Output: true


Example 3:

Input: "(]"
Output: false


Example 4:

Input: "([)]"
Output: false


Example 5:

Input: "{[]}"
Output: true


## Notes

An empty string is also considered valid.

## Solution

\documentclass{article}
\usepackage[a3paper, landscape]{geometry}
\usepackage{newtxtext, newtxmath}
\usepackage{amsmath}
\usepackage{datetime2}
\usepackage{expl3}

\begin{document}

\ExplSyntaxOn

\str_new:N \l_tmpc_str

\prop_new:N \g_paren_prop
\prop_gput:Nnn \g_paren_prop {[} {]}
\prop_gput:Nnn \g_paren_prop {(} {)}
\prop_gput:NVV \g_paren_prop {\c_left_brace_str} {\c_right_brace_str}

\par\cs_meaning:N \g_paren_prop

\tl_new:N \g_result_tl

\cs_new:Npn \is_paren_valid:n #1 {
\seq_gclear:N \g_tmpa_seq
\str_gset:Nn \g_tmpa_str {#1}
\exp_args:NNV \str_gremove_all:Nn \g_tmpa_str {\space}

\par processed~input:~\str_use:N \g_tmpa_str
\str_map_variable:NNn \g_tmpa_str \l_tmpa_str {
\prop_if_in:NVTF \g_paren_prop \l_tmpa_str {
% left parenthesis encountered
\seq_gput_left:NV \g_tmpa_seq \l_tmpa_str
} {
% right parenthesis encountered
\seq_get_left:NNTF \g_tmpa_seq \l_tmpb_str {
% \l_tmpb_str is the head (last left parenthesis)
% get corresponding right string from prop list
\prop_get:NVN \g_paren_prop \l_tmpb_str \l_tmpc_str
\str_if_eq:VVTF \l_tmpa_str \l_tmpc_str {
\seq_gpop_left:NN \g_tmpa_seq \l_tmpa_tl
} {
% if parenthesis mismatch, return false
\tl_gset:Nn \g_result_tl {false}
\str_map_break:
}
} {
% if the sequence is empty, return false
\tl_gset:Nn \g_result_tl {false}
\str_map_break:
}
}
}
\seq_if_empty:NTF \g_tmpa_seq {
\tl_gset:Nn \g_result_tl {true}
}{
\tl_gset:Nn \g_result_tl {false}
}
}

\cs_generate_variant:Nn \is_paren_valid:n {x}

\is_paren_valid:x {\c_left_brace_str  [ (()) ] \c_right_brace_str}
\par \textbf{result:~\tl_use:N \g_result_tl}
\is_paren_valid:x {(}
\par \textbf{result:~\tl_use:N \g_result_tl}
\is_paren_valid:x {[[((()))]]}
\par \textbf{result:~\tl_use:N \g_result_tl}
\is_paren_valid:x {([)]}
\par \textbf{result:~\tl_use:N \g_result_tl}

\ExplSyntaxOff

\par\DTMNow

\end{document}


## Output

macro:->\s__prop \__prop_pair:wn [\s__prop {]}\__prop_pair:wn (\s__prop {)}\__prop_pair:wn {\s__prop {}}
processed input: {[(())]}
result: true
processed input: (
result: false
processed input: [[((()))]]
result: true
processed input: ([)]
result: false
2020-06-15 12:43:28-04:00