Python. 어떻게 예를 들어, 입력 문자열의 경우 문자열

Question

에 중복/잘못된 괄호를 제거 : 결과

s = "fo)o)fus()(bar((em)ro(em))dah((y(XXX)"

를 나는 기대 : 그것은 결과처럼

fus()((em)ro(em))dah(XXX)

모든 "건강한"블록을 포함해야 , 그들 사이에 열린 "("및 닫힌 ")"+ "건강한"텍스트가 있습니다. "()"에 관여하지 않고 "()"사이에 없거나 "()"에 포함되어 있지 않기 때문에 모든 아픈 부분을 제거해야합니다 (0123) 검사 예 :

z = "))(OMG)123(()qwe(zxc)(ll"

이 (OMG)123()qwe(zxc)

나는 그것이해서 같은 re 모듈로 해결 될 수 있다는 것이다 반환해야합니다. 하지만 어떤 알고리즘을 사용해야하는지 잘 모르겠습니다.

추신 : 나는 어떤 도움도 거부하지 않을 것입니다. :)

Answer 1

스택을 사용하는 데 대한 좋은 예가 있으며 거의 ​​모든 CS 학생이이 문제를 적어도 한 번 해결했습니다. 예를 들어 this을 확인하십시오. 그러나 더 나은 구문 (특히 C++ 용으로 작성된 구문)을 찾을 수 있습니다.

이러한 솔루션은 일반적으로 문이 정확한지 확인하는 데 사용되지만 동일한 논리를 사용하여 잘못된 부분을 제거하고 일치하는 문구 만 저장하면됩니다. 그래서 그냥 새로운 문자열 변수 (variable="")를 만들고, 문자열을 반복하고, 괄호를 확인하십시오. 올바른 위치에 있으면 변수에 추가하십시오. 괄호 순서를 검사하려면 Stack 객체를 사용합니다. 괄호를 열면 스택에 밀어 넣은 다음 스택을 닫고 스택에서 마지막 값을 팝합니다 (새 항목은 )이고 스택의 마지막 항목입니다). (이어야합니다. 일치하지 않으면 그 부분을 버리고 계속해서 일치하면 해당 부분을 문자열에 추가하십시오.