산술 표현식을 작성하는 방식을 표기법(notation)이라고 부릅니다. 하나의 산술 표현식은 식의 본질이나 계산 결과를 전혀 바꾸지 않으면서도 서로 다른 세 가지 방식으로 표현할 수 있습니다. 이 세 가지 표기법은 다음과 같습니다.
- 중위 표기법(Infix)
- 전위 표기법(Prefix)
- 후위 표기법(Postfix)
중위 표기법은 우리가 일상적으로 수학식을 작성할 때 사용하는 표준적인 방식입니다. 반면 전위 표기법과 후위 표기법은 컴퓨터가 식을 처리하기에 훨씬 유리한 형태로, 괄호 없이도 연산 순서를 명확하게 나타낼 수 있다는 큰 장점이 있습니다.
전위 표기법(Prefix Notation)
전위 표기법에서는 연산자가 피연산자 앞에 위치합니다. 즉, 연산자를 피연산자보다 먼저 작성하는 방식입니다. 예를 들어 +ab는 중위 표기법 a + b와 동일한 의미를 가집니다. 전위 표기법은 폴란드 표기법(Polish Notation)이라고도 불리며, 폴란드의 논리학자 얀 루카시비치(Jan Łukasiewicz)가 고안한 것으로 잘 알려져 있습니다.
후위 표기법(Postfix Notation)
후위 표기법은 역폴란드 표기법(Reverse Polish Notation)이라고도 알려져 있습니다. 이 방식에서는 연산자가 피연산자 뒤에 위치합니다. 예를 들어 ab+는 중위 표기법 a + b와 같은 의미입니다.
표기법 변환 예시
| 번호 | 중위 표기법 | 전위 표기법 | 후위 표기법 |
| 1 | a + b | + a b | a b + |
| 2 | (a + b) * c | * + a b c | a b + c * |
| 3 | a * (b + c) | * a + b c | a b c + * |
| 4 | a / b + c / d | + / a b / c d | a b / c d / + |
| 5 | (a + b) * (c + d) | * + a b + c d | a b + c d + * |
| 6 | ((a + b) * c) - d | - * + a b c d | a b + c * d - |
표현식 파싱(Parsing Expression)
앞서 살펴본 것처럼, 중위 표기법을 그대로 해석하도록 알고리즘이나 프로그램을 설계하는 것은 효율적이지 않습니다. 중위 표기법에는 괄호와 연산자 우선순위가 얽혀 있어 처리 과정이 복잡하기 때문입니다. 그래서 실제로는 중위 표현식을 먼저 후위 또는 전위 표기법으로 변환한 뒤 계산하는 방식을 사용합니다. 특히 후위 표기법은 스택(stack) 자료구조를 활용하면 왼쪽부터 차례대로 한 번의 순회만으로 값을 계산할 수 있어, 컴파일러와 전자계산기 구현에 널리 활용됩니다.
산술 표현식을 올바르게 파싱하려면 연산자 우선순위(precedence)와 결합 법칙(associativity)을 함께 고려해야 합니다.
연산자 우선순위(Precedence)
하나의 피연산자가 서로 다른 두 연산자 사이에 놓일 때, 어떤 연산자가 그 피연산자를 먼저 처리하는지는 연산자 간의 우선순위에 따라 결정됩니다. 예를 들어 다음과 같습니다.
a + b * c → a + (b * c)
곱셈(*)이 덧셈(+)보다 우선순위가 높기 때문에 b * c가 먼저 계산됩니다. 참고로 주요 연산자의 우선순위는 다음과 같습니다.
- 높음: 지수(^)
- 중간: 곱셈(*), 나눗셈(/), 나머지(%)
- 낮음: 덧셈(+), 뺄셈(-)