스택(Stack) - 전위 표기법(prefix notation), 중위 표기법(infix notation), 후위 표기법(postfix notation)

<전위 표기법(prefix notation)>

연산자를 피연산자를 앞에 표기하는 방법
예) +AB

중위 표기를 전위 표기법으로 바꿔보자.

① 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

② 각 연산자를 그에 대응하는 왼쪽괄호의 앞으로 이동시킨다.

③ 괄호를 제거한다.​

<중위 표기법(infix notation)>

연산자를 피연산자의 가운데 표기하는 방법
예) A+B

 

<후위 표기법(postfix notation)>

연산자를 피연산자 뒤에 표기하는 방법

예) AB+

중위 표기를 후위 표기법으로 바꿔보자.

① 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
② 각 연산자를 그에 대응하는 오른쪽괄호의 뒤로 이동시킨다.
③ 괄호를 제거한다.

<스택을 사용한 후위표기식으로 변환>

⑴ 왼쪽괄호를 만나면 무시하고 다음 문자를 읽는다.
⑵ 피연산자를 만나면 출력한다.
⑶ 연산자를 만나면 스택에 push한다.
⑷ 오른쪽괄호를 만나면 스택을 pop하여 출력한다.
⑸ 수식이 끝나면, 스택이 공백이 될 때까지 pop하여 출력한다.

[코드]