명제 논리 프로그램에서 괄호 구문 분석

저는 명제 논리 구문을 결합 표준 형태로 변환하기 위해이 과제를 진행하고 있습니다. 문제는 복잡한 괄호 수준을 파싱하는 것입니다. 문제는 올바른 순서로 해결되어야하며 외부로 이동하기 전에 내부 괄호를 먼저 푸는 데 재귀를 사용해야하지만 생각을 구현하는 방법을 알 수는 없다고 생각합니다. 이 프로그램은 Java로 작성해야합니다. 누구든지 도와 줄 수 있습니까?명제 논리 프로그램에서 괄호 구문 분석

출처

2012-04-30 Rambo8000

나는 반 (半) 중첩 적으로 작업을 시도한 펑키 한 시스템을 가지고있었습니다. 그것은 처음부터 시작하려하고, 첫 번째 열린 괄호를 찾아 첫 번째 닫기 괄호까지 모든 것을 가져 와서 하나의 열린 괄호와 하나의 닫힌 괄호가있을 때까지 재귀 적으로 먹이려고합니다. 그런 다음 해결하려고합니다. 내가 가진 문제는 해결할 때, 때로는 더 많은 괄호가 필요하므로 메서드가 루프에 걸릴 수 있습니다. 그것과 나는 논리를 끝내지 않았으므로 그것을 시험 할 수 없었다. – Rambo8000

http://stackoverflow.com/questions/15982087/how-to-convert-statements-into-cnf/15982562?noredirect=1#15982562 – user2260056

[비슷한 질문 ....(하지 않은지 (NOT A)), (NOT (NOT (OR (AB)))] [1] [: 그래서, 우리는 IF-ELSE 모든 가능한 입력 등을 위해 같이 사용하여 코드를 작성해야 할 1] : http://stackoverflow.com/questions/15982087/how-to-convert-statements-into-cnf/15982562?noredirect=1#15982562 – user2260056

의사 코드 : 당신에게 힌트를 줄

parseRestOfString (int openParens, String rest) { 
    c = rest (0); 
    if (c == ')' && openParens == 0) ...

합니까?

출처

2012-04-30 19:23:22

의사 코드에 대한 한 가지 질문 : 콜론이 " String "은"for-loop "또는 문자열 배열을위한 할당 또는 속기입니까? – Rambo8000

Java와 유사한'int (int openParens, scala like,'rest : String)'혼합물이 있습니다. –

CNF로 변환하는 문장의 예를 들려 줄 수 있습니까? 나는 당신이 시작 논리 문장에 괄호가 있다는 것을 의미한다고 생각하고 있지만 도움이 될 것입니다.

한편, 재귀가 필요 없다고 말할 것입니다 ...하지만 스택이 도움이 될 것입니다 :) 스택에 항목과 수학 연산을 푸시 한 다음 적절히 팝업하여 적절하게 조치를 취하십시오 . 숙제이기 때문에 자세히 설명하지는 않겠지 만, 푸시 푸시 - 푸시 - 팝 - 멀티 - 푸시 - 푸시 - 팝 - 추가 - 팝 - 나누기 ... 스택을 다음과 같이 사용하십시오. 현재 작업에 초점을 맞추는 방법.

Postfix Notation에 대한 조사도 관련이 있으며 도움이 될 것입니다 ... 위키 피 디아의 기사조차도 당신에게 아이디어를 줄 것입니다 (컴퓨터 과학에 관한 기사가 절대적으로 많지만).

면책 조항 :) 당신은을 통해 두 개 이상의 패스를 필요가 없습니다

업데이트 : 내 예에서와 푸시와 팝의 수 또는 순서로 어떤 생각을 넣지 데이터 및 CNF로 즉시 변환 할 수 있습니다.

당신은 올바른 방향으로 가고, 그래서 도움/힌트하고 있습니다 :

를 사용하여 두 스택, 피연산자 다른 하나는 사업자를.

두 개의 피연산자와 연산자가있는 경우 피연산자를 팝하고 연산자를 적용한 다음 결과를 새로운 (통합 된) 피연산자로 푸시하십시오.

변환의 이점은 즉시 수행 할 수 있다는 것입니다 ... 당신이 →가 발생하는 경우, 예를 들어, 피연산자 스택에 ¬을 적용하고 귀하의 예제의 감소 촬영 운영자 스택

위에 ⋁를 밀어 :

F→(E⋀(A→B))

첫 번째 단계를 전환의 (나는 당신이 유엔을 가지고 있다고 가정하고 있어요. 로직 변환을 derlying하는 팻 다운 규칙, 그리고 당신이) 운동하고 바로 코드 있다고 :
CNF 접미사에서
F→(E⋀(A→B)) ¬F⋁(E⋀(A→B)) ¬F⋁(E⋀(¬A⋁B))

, 그것은 다음과 같이 표시됩니다

F¬EA¬B⋁⋀⋁ // (Parentheses are obviated in postfix notation)

거기까지 읽고, 첫 번째 논리 구문을 통해 왼쪽에서 오른쪽으로 한 번에 피연산자를 피연산자 스택에 넣고 연산자를 연산자 스택에 넣습니다.

연산자를 적용 할 때 피연산자 스택에서 필요한 피연산자를 팝하고 연산자를 적용한 다음 결과 문자열을 새 피연산자로 스택에 다시 푸시합니다.

닫는 괄호 또는 낮은 우선 순위 연산이 pop-apply-push를 트리거합니다. 모든 것은 다음과 같습니다

Operand Operator Stack Stack ---------- ---------- Read F: Push onto Operand stack F ........ .......... Read →: On-the-fly conversion (→ becomes ¬⋁) Unary Operator ¬ pops F from Operands; applies it; pushes back to Operands ¬F ....... .......... Push ⋁ onto the op-stack ¬F ....... ⋁ ....... Read (: Discard Read E: Push onto Operands stack ¬F E .... ⋁ ...... Read ⋀: Push onto Operators stack ¬F E .... ⋁⋀ ..... Read (: Discard Read A: Push onto Operands stack ¬F E A .. ⋁⋀ ..... Read →: On-the-fly conversion (→ becomes ¬⋁) Unary Operator ¬ pops A from Operands; applies; pushes back to Operands ¬F E ¬A . ⋁⋀ ..... Push ⋁ onto Operators stack ¬F E ¬A . ⋁⋀⋁ .... Read B: Push onto Operands stack ¬F E ¬A B ⋁⋀⋁ .... Read): Triggers Operators/Operands pop; applies; pushes back to Operands (After, there are three operands on the Operands stack) ¬F E (¬A⋁B) ⋁⋀ .... Read): Triggers Operators/Operands pop; applies; pushes back to Operands (After, there are two operands on the Operands stack) ¬F (E⋀(¬A⋁B)) ⋁ .... No more reads: Final Operators/Operands pop/apply/push (result is output) ¬F⋁(E⋀(¬A⋁B))

주의 사항 및 참고 사항 :

이 ... 당신은 연산자 우선 순위와 같은 문제를 처리해야 올바른 방향으로 단지 시작이다 (즉 당신은 나중에 밀고 행동하거나 팝하고 행동하십시오). 당신은 당신이 읽은 다음 글자를 기반으로 결정을 내린다는 것을 알게 될 것입니다 (위에서 묵시적으로 말한 것처럼 닫는 괄호는 아닙니다).

위의 코드에 대한 의사 코드는 12-15 줄을 넘지 않습니다. 그러나, 내가 언급하지 않은 복잡성이 있습니다 ... < -> 함수는 위에서 말한 것과 비슷한 방식으로 모델링되어야합니다 ... 당신은이 사고 방식을 취해야하고 모든 것을 구현해야합니다. 전환 규칙

괄호 안에 내포 된 괄호가 표시됩니다.

6 * (8 * 6) + 4

는 제대로 연산자 우선 순위를 처리하지 않는 경우, 대신 정답, 당신에게 (312)을 제공

686*4+*

처럼 뭔가 끝낼 수 있습니다 정말

(6 * (8 * 6)) + 4

입니다 (292).

이 게시물의 유니 코드 논리 기호를 읽는 데 문제가 있으면 알려주십시오. 나는 표준 문자를 다시 할 수 있지만, 유니에 훨씬 더 좋은 읽습니다)

HTH,
제임스

가 PS : 맵시 작은 애플릿 설명 접미사가 여기에 있습니다 :
http://fac-web.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/

출처

2012-04-30 19:27:39

예는 다음과 같습니다. F -> (E/\ (A -> B) <-> (C -> D)) 여기서 "->"는 의미를 의미하고 "<->"는 양심적 인 ional이고, "/ \"는 결합을 의미합니다. – Rambo8000

좋아요, 제가 말한 모든 것이 적용됩니다. 스택 및 후치 표기법을 읽으 려합니다 ... 일반적인 생각은 여기에 있습니다 : http://en.wikipedia.org/wiki/Postfix_notation#Explanation - 여전히 도움이 필요할 때 도움을 제공 할 수 있습니다. 당신의 머리를 긁적 ... 당신에게 '대답'을주기 전에 아이디어를 조금 생각할 기회를주고 싶습니다. 조금이라도 읽고 그것을 적용하는 방법을 생각하면 위대한 정신 운동입니다 ... 학교를 나가기 전까지는 정교하게 연마 될 수있는 능력이 필요합니다.) –

정말 도움이됩니다. 그래서 스택과 포스트 픽스를 모두 살펴 보았습니다. 필자는 포스트 픽스가 어떻게 여기에 사용되는지, 왜 원래 포맷보다 선호되는지 확실하지 않습니다. 나는 스택을 사용하기 시작했는데 여전히 꼬임을 풀려고 노력하고 있습니다. 스택 전체를 문제로 쌓아 내려고 노력한 다음, 다음 괄호 세트를 사용하여 스택이 다음과 같이 보이도록했습니다. F -> (E/\ (A -> B) <-> (C- -> D)) then E/\ <-> (C -> D) ... 그리고 바닥에 도달하면 다시 풀리고 다시 올라갑니다. 그것은 어쨌든 아이디어입니다. 나는 최선의 방법으로 구현하는지 잘 모르겠다. – Rambo8000

이것 좀보세요 :

Recursive descent parser

JavaCC

출처

2012-04-30 19:34:44 ceklock

명제 논리 프로그램에서 괄호 구문 분석

답변

관련 문제