: 임프님 천리안 PDSPF의 답변( 1555번 ) 감사합니다.
:
: 임프님의 홈페이지에 처음 와 보는데 좋은 자료들이
: 많아 감사드립니다.
:
: 답변 내용중에
:
: "문자열 수식을 파싱하려고 하시는군요....
:  괄호 연산자를 처리해야 하므로, 여러가지 알고리즘 중에서 스택 알고리즘을 선택하는..."
: 이라는 내용이 있는데 구체적인 예를 들어주시면 안될까요?
:
: SQL 문의 where 조건 도 스택알고리즘을 사용하는 겁니까 ?
:
: 답변 기다리겠습니다.
:
: 감사합니다.



임펠리테리입니다.

프포에서 드렸던 답변이 참고가 되었는지 모르겠군요. 저도 아주 오래전에..(92년 쯤이었나?)
작성해봤던 소스라서, 구체적으로 답변을 드리기가 곤란해서 개략적으로만 알려드린 건데요.
일단 생각나는대로 알려드리겠습니다.

문자열 수식 파싱의 방법은 여러가지가 나와있지만, 제가 사용했던
방법이 가장
쉽고 많이 사용되는 방법이었다고 알고 있습니다.
가장 먼저, 일단 문자열 자체를 앞에서부터 뒤로 진행하면서 문자열의 각 요소들을
직접 연산할 수 있는 토큰들로 바꿉니다. 토큰이란 별다른 대단한 것이 아니고,
연산식에서 연산자들과 피연산자들을 각각 프로그래머가 사용하기 쉬운 의미있는
값들로 바꾸는 것입니다.
그리고... 이렇게 변환된 토큰들의 배열을 가지고 다음 작업을 합니다.
논리연산이든 수치연산이든, 우리가 일반적으로 사용하는 수식들은 보통 중위 연산식으로
되어있습니다. 중위 연산이란.. in-fix라고 하는데, 피 연산자가 둘일때 연산자가
가운데에 위치하기 때문에 부르는 이름입니다. 예를 들어서,
1 + 3
이라는 예에서, 연산자 '+'는 피연산자 '1'과 '3'의 가운데에 위치합니다.
하지만, 이러한 중위연산식은 그대로 처리하기가 곤란하죠. 물론 제가 줏어듣기로는
중위연산식을 그대로 연산하는 방법도 있다고 알고 있습니다만, 알고리즘이 훨씬
더 복잡해지는 것은 뻔할 겁니다. 그래서 연산식의 배열을 좀 바꾸어 전위연산식으로
변환하여 사용합니다. 전위연산, pre-fix는, 연산자와 피연산자의 배열을 바꾸어,
연산자가 피연산자보다 앞에 위치하도록 배치한 것입니다.
1 + 3 이라는 연산식은 pre-fix로 변환하면
+ 1 3
과 같이 됩니다. 만약 좀 더 긴 수식으로,
1 * (3 + 5)
와 같은 수식이라면,
* 1 + 3 5
와 같이 됩니다.
이렇게 pre-fix 연산식으로 변환하기 위해서는 보통 스택 알고리즘을 사용합니다.
pre-fix로 변환된 연산식을 최종 결과값으로 계산하기 위해서는 스택이나 다시
스택이나 이진트리를 사용해서 계산합니다.

앞에서 말씀드렸다시피, 이와같은 계산기 형태의 문자열 수식 파싱은 해본지가
너무 오래되었고, 지금 제게 참고할 만한 서적도 없는 상태라서 구체적으로 답변을
드리기가 힘듭니다. 또 저는 전산 전공도 아니었고, 전자 전공으로 단지 흥미가 있어서
잠시 작성해본 프로그램이었으니까요. 전산과 계통의 전공 과목에 알고리즘이나
프로그래밍 관련 다른 과목들 중에 이러한 파싱을 이론적으로 가르치는 과목이 있는
걸로 알고 있습니다. 그쪽 전공 서적을 참고하시거나.. 혹은 문자열 파싱에 관련된
아티클들은 웹에서도 쉽게 발견하실 수 있을 겁니다.

그럼 참고하시길...