[Data Structure/자료구조] 전위 중위 후위 표기법(Prefix, Infix, Postfix)

전위 중위 후위 표기법(Prefix, Infix, Postfix) 에 대해 설명하고, 이를 스택을 활용해서 계산하는 방법에 대해 설명해 주세요.

전위표기법(Prefix)

• 형태: +AB
• 연산자를 먼저 표시하고 연산에 필요한 피연산자를 나중에 표기하는 방법이다.

중위표기법(Infix)

• 형태: A+B
• 연산자를 두 피연산자 사이에 표기하는 방법으로 가장 일반적으로 사용되는 표현 방법이다.

후위표기법(Postfix)

• 형태: AB+
• 피연산자를 먼저 표시하고 연산자를 나중에 표시하는 방법이다.
• 컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장한다.
• 스택을 사용한 계산 방법 숫자를 만나면 전부 스택에 집어 넣는다. -> 연산자가 나오면 스택에서 두 수를 꺼내 계산하고 다시 스택에 집어 넣는다.
  
  • 스택을 사용한 계산 방법:
    1. 숫자가 나오면 그대로 출력한다.
    2. ( * / 나오면 스택에 push한다.
    3. + - 연산이 나오면 여는 괄호(, 여는 괄호가 없다면 스택의 끝까지 출력하고 그 연산자를 스택에 push한다.
    4. 닫는 괄호)가 나오면 여는 괄호(가 나올때까지 pop하여 출력한다.