删除表达式树中第一个元素周围和Python中每个子表达式树中的括号
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了删除表达式树中第一个元素周围和Python中每个子表达式树中的括号,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2298字,纯文字阅读大概需要4分钟。
内容图文
目标是实现简化操作:删除表达式树及其每个子表达式树中第一个元素周围的括号,其中表达式作为包含在各种括号中的字符串输入给出.这必须适用于任意数量的括号,例如:
(12)3((45)6) – > 123(456),删除括号约12然后约45
((12)3)4(((5)67)8) – > 1234(5678),删除12左右的括号,然后是123,然后是5,然后是567.不要删除5678左右的括号,因为那是第二个元素.
我该怎么做呢?
编辑:到目前为止我所拥有的是:
def simplify(expression):
"""
call itself recursively until no consecutive parentheses exist
"""
result = []
consec_parens = 0
inside_nested = False
for char in expression:
if char == ')' and inside_nested:
inside_nested = False
consec_parens = 0
continue
if char == '(':
consec_parens += 1
else:
consec_parens = 0
if consec_parens == 2:
inside_nested = True
else:
result.append(char)
result = ''.join(result)
if result == expression:
return result
return simplify(result)
它适用于嵌套括号的数量至少为2的所有情况,但它对头部不起作用,即对于(AB)C,它不会删除AB周围的括号.但是,对于((AB)C),它删除了AB周围的括号,导致(ABC).
解决方法:
这可以看作是一个有限状态机(有三个状态),你可以在每个级别实例化一次,其中每个(符号创建一个新的级别.或者,它是一个确定性的pushdown automaton,有两个平凡的状态(一个进行中的状态和一个完成)状态,我们都没有显式建模)和三个堆栈符号,每个符号表示当前级别的机器状态:
>之前 – 我们进入一个级别后立即进入的状态.遇到任何字符,除了)转换到其他状态.
>内部 – 我们所处的状态,而在括号内需要删除.通过装饰来进入(在之前.
>完成 – 处理当前级别时我们所处的状态.这意味着我们已经删除了一组括号或者我们不需要,因为第一个元素没有包含在它们中.
此外,遇到a(将新符号推入堆栈,模型进入新级别,以及a)从中弹出一个符号,这些模型从一个级别离开.除非发生Before→Inside和Inside→Done转换,否则所有输入字符都会附加到结果上.
以下代码是上面对Python的简单翻译:
from enum import Enum
class State(Enum):
Before = 0
Inside = 1
Done = 2
def simplify(expression):
levels = [State.Before]
result = []
for c in expression:
if c == '(':
if levels[-1] == State.Before:
levels[-1] = State.Inside
else:
result.append(c)
levels.append(State.Before)
elif c == ')':
levels.pop()
if levels[-1] == State.Inside:
levels[-1] = State.Done
else:
result.append(c)
else:
if levels[-1] == State.Before:
levels[-1] = State.Done
result.append(c)
return ''.join(result)
测试以上,我们得到:
>>> simplify('(12)3((45)6)')
'123(456)'
>>> simplify('((12)3)4(((5)67)8)')
'1234(5678)'
>>> simplify('(AB)C')
'ABC'
>>> simplify('((AB)C)')
'ABC'
内容总结
以上是互联网集市为您收集整理的删除表达式树中第一个元素周围和Python中每个子表达式树中的括号全部内容,希望文章能够帮你解决删除表达式树中第一个元素周围和Python中每个子表达式树中的括号所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。