[Algorithm] 후위표현식? stack?

오늘은 표현식/ 표기법 알고리즘에 대해 정리해보겠습니다 :)

 

📍 계기

표기법에 대해 가장 먼저 알게 되었을 때는 정보처리기사 시험을 준비하면서 접하였습니다.

그 후 백준 1935번 문제를 마주하게 되었고, 후위표현식 관련 알고리즘을 다뤘습니다. 

 

📍 설명

표기법 즉, 표현식에는 전위(prefix) / 중위(infix) / 후위(postfix) 표기법으로 나뉩니다.

1. 전위 표기법

연산자를 먼저 표기하고 연산자가 필요한 피연산자를 나중에 표기하는 방법

ex) +12

 

2. 중위 표기법

연산자를 두 피연산자 사이에 표기하는 방법으로 가장 일반적으로 사용되는 표현 방법

ex) 1+2

 

3. 후위 표기법

피연산자를 먼저 표시하고 연산자를 나중에 표기하는 방법이다.

컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장한다.

ex) 12+

 

✔️ 자료구조 stack을 이용하기 풀이 방법

1. 표현식에서 숫자로 된 피연산자는 stack에 모두 넣기

2. 연산자가 나오면 스택에서 두 수를 꺼내 계산하고 다시 스택에 집어 넣기