A new Parallel Algorithm for the Parentheses-Matching Problem

1 The parentheses-matching problem is of crucial importance in the construction of expression tree in order to evaluate, for instance, arithmetic expressions. A new parallel algorithm is introduced in this paper to solve the parenthesesmatching problem optimally (in O(log 2 n) parallel time with O(n= log 2 n) processors) on an EREW-PRAM model. An algorithm for an input string of n parentheses with a maximal nested level of log n is also presented. Keywords: parallel algorithms on PRAM (Parallel Random Access Machine) model, parentheses-matching problem. 1 Introduction The parentheses-matching problem, initially tackled in [1], is used to determine the mate of each parenthesis in a balanced string of n (opening or closing) parentheses. The parentheses are matched with a sequential algorithm in O(n) time complexity using a stack by scanning the string once. One can view the parentheses-matching problem as a subproblem of parsing, recognition (over a 2 letters alphabet) of formal lang..