[Day2] 스택의 응용 - 수식의 후위 표기법(Postfix Notation)
스택의 응용 - 수식의 후위 표기법
중위 표기법(Infix Notation)
- 연산자가 피연산자들의 사이에 위치
- (A + B) * (C + D)
후위 표기법(Postfix Notation)
- 연산자가 피연산자들의 뒤에 위치
- AB + CD + *
예시
A * B + C
- 연산을 만나면 스택에 집어 넣는다
- 스택에 있는 연산자는 아직 표현되지 못한 연산자들이다.
- 을 스택에 저장 하고 나서, +를 만나면 우선순위가 가 높기 때문에 *는 스택에서 탈출한다. 즉, 스택안에서 우선순위가 유지되어야 하고 유지 되지 못하면
pop
을 하게 된다.
pop
을 하게 된다.A + B * C
- '+'을 넣고 나서, ''연산자를 만났을 때, 우선순위가 가 높기 때문에 일단 스택에 저장한다. *을 넣어도 우선 순위가 유지되기 때문에 일단 넣고 본다.
A + B + B
- 동일한 연산자를 만나게 되면 우선순위가 깨졌다고 판단하고, 스택에서
pop
을 한다.
괄호의 처리
예시1
[중위] (A + B) * C
[후위] A B + C *
- 여는 괄호는 스택에 push
- 닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop
→ 괄호안에 있는 내용들 먼저 pop
예시2
[중위] A * (B + C)
[후위] A B C + *
-
연산자를 만났을 때, 여는 괄호 너머까지 pop 하지 않도록
-
여는 괄호 우선순위는 가장 낮게 설정
알고리즘의 설계
- 연산자의 우선순위 설정
prec = {
'*' : 3,
'/' : 3,
'+' : 2,
'-' : 2,
'(' : 1 # 괄호는 우선 순위가 가장 낮게
}
-
중위 표현식을 왼쪽부터 한 글자씩 읽어서
- 피연산지연 그냥 출력
-
(
이면 스택에 push
-
)
이면 )
이 나올 때까지 스택에서 pop
그리고 출력
-
연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을 pop
그리고 출력
- 그리고 이 연산자는 스택에
push
-
스택에 남아 있는 연산자는 모두 pop
그리고 출력
Author And Source
이 문제에 관하여([Day2] 스택의 응용 - 수식의 후위 표기법(Postfix Notation)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@metterian/Day2-스택의-응용-수식의-후위-표기법Postfix-Notation
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
prec = {
'*' : 3,
'/' : 3,
'+' : 2,
'-' : 2,
'(' : 1 # 괄호는 우선 순위가 가장 낮게
}
중위 표현식을 왼쪽부터 한 글자씩 읽어서
- 피연산지연 그냥 출력
-
(
이면 스택에push
-
)
이면)
이 나올 때까지 스택에서pop
그리고 출력 -
연산자이면 스택에서 이보다 높(거나 같)은 우선순위 것들을
pop
그리고 출력- 그리고 이 연산자는 스택에
push
- 그리고 이 연산자는 스택에
스택에 남아 있는 연산자는 모두 pop
그리고 출력
Author And Source
이 문제에 관하여([Day2] 스택의 응용 - 수식의 후위 표기법(Postfix Notation)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@metterian/Day2-스택의-응용-수식의-후위-표기법Postfix-Notation저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)