在圆括号字符串验证程序中，堆栈的push和pop操作在每次迭代中是如何发生的

Question

这里使用字典键作为开括号，值作为结束符括号。怎么做它真的在堆栈中工作吗？你知道吗

 class py_solution:

    def is_valid_parenthese(self, str1):
        stack=[] 
        pchar = {"(": ")", "{": "}", "[": "]"}
        for parenthese in str1:
            if parenthese in pchar:
                 stack.append(parenthese)

            elif len(stack) == 0 or pchar[stack.pop()] != parenthese:


                return False
        return len(stack) == 0


st=raw_input("Enter string of parenthesis")
print(py_solution().is_valid_parenthese(st))

Answer 1

通常，表达式的解析器是使用递归函数实现的，因此函数将递归地调用自身或其他函数来解析子表达式、获取其结果并构建子表达式的复合表达式，而不是循环（如您或Patrick的示例中所示）。你知道吗

然后，您的代码不会显式地处理堆栈，而是使用常规执行堆栈来实现这一点。你知道吗

看看这个实现：

class Named_List(list):
  def __repr__(self):
    return '%s(%s)' % (type(self).__name__, ', '.join(repr(x) for x in self))

class Parens(Named_List): pass

class Brackets(Named_List): pass

class Braces(Named_List): pass

def parse(text):
  if not text:
    raise Exception("empty input")
  result = []
  if text[0] == '(':
    text = text[1:]
    while text[0] != ')':
      element, text = parse(text)
      result.append(element)
    return Parens(result), text[1:]
  elif text[0] == '[':
    text = text[1:]
    while text[0] != ']':
      element, text = parse(text)
      result.append(element)
    return Brackets(result), text[1:]
  elif text[0] == '{':
    text = text[1:]
    while text[0] != '}':
      element, text = parse(text)
      result.append(element)
    return Braces(result), text[1:]
  else:
    raise Exception("bad input", text)

此函数返回给定括号表达式及其无法分析的部分的抽象语法树（AST）。对于'(((()[]{})))'这样的输入，它将返回Parens(Parens(Parens(Parens(), Brackets(), Braces())))（以及空字符串，因为它可以解析所有内容）。对于像'(((()[]{)))'这样的错误输入，它将引发一个异常，抱怨不好的rest ')))'不再可解析。你知道吗