식처리기의 기초가 되는 기본값 파싱과 연산처리기를 다뤘으므로 이제 괄호구문을 포함하는 식의 스택(stack)구조 처리기를 만들어볼 차례입니다.
스택처리기를 이미 만들어보신 적이 있다면 내용은 일반적인 스택처리기와 대동소이하므로 가볍게 읽으실 수 있습니다.
내용이 어렵지는 않지만 순차적인 진행이 필요하므로 반드시 앞에 글부터 보시길 바라고 오랜만에 보시는 분들도 복습 한 번 하시고 보시는 편이 좋습니다(저도 앞에 글 보고 쓰는 중 ^^)
식에서 스택이 만들어지는 이유
하나의 식에서 스택구조가 생성되는데는 다양한 이유가 있습니다. 쨌든 그 다양한 경우는 간단히 한 가지로 정리할 수 있는데
우선 처리해야 할 것
이 존재하면 무조건 스택구조가 필요합니다. 식에서 먼저 처리해야하는 것 하면 곧장 떠오르는건 연산자 우선순위겠지만 그건 이미 1 / 3 에서 처리했습니다. 그렇다면 어떤 것들이 남아있을까요.
의외로 굉장히 많습니다. 다음은 그러한 예를 나타내고 있습니다.
- 괄호연산자를 통한 강제 우선순위 지정 : ( 1 + 3 ) * 2 → 괄호 내부를 먼저 처리해야 함
- 함수 호출처리를 위한 인자의 우선처리 : a( b(), c() ) * 3 → a의 인자인 b와 c의 호출을 먼저 처리하고 a의 호출을 처리한 뒤에나 3을 곱할 수 있음
- 모든 리터럴처리 : [1,2,3], {a:1, b:3}, /^[0-9]+$/, function(){} 등 → 모든 리터럴은 연산식이 발동되기 전에 먼저 처리되어야 함
- 점연산자, 대괄호연산자 : arr[3], obj[‘key’], obj.key → 객체의 속성을 찾는 점, 대괄호 연산은 연산식 이전에 먼저 처리되어야 함
게다가 스택을 발생시키는 요소 간에도 우선 순위가 등장합니다. 결국 스택이란 우선 해야할 일이 있다는 뜻이고 그것은 우선 처리할 일을 하는 동안에 다른 부분은 기억을 해둬야 한다는 뜻입니다.
이것이 바로 스택이 별도의 메모리를 필요로 하는 이유이기도 합니다.
스택의 처리방법
식에 등장하는 스택에 대해서 반드시 인지해야할 것은 바로 스택처리의 목표입니다. 식처리기의 다른 부분과 마찬가지로 스택처리기도 식처리기와 동일한 목표를 갖고 있습니다.
하나의 값에 수렴시킨다
입니다. 결국 스택은 전부 해소되고 나면 하나의 값이 됩니다. 또한 우선 순위가 있다는 뜻을 뒤집어서 생각해보면
미뤄둘 수 있다
라고 생각할 수도 있다는 점입니다.
위의 두 가지 속성(값에 수렴, 미룬다)을 이용해 스택을 처리하는 연습을 예제로 해보죠. 아래 식은 괄호를 중첩되게 써서 스택을 발생시키고 있습니다.
3 * ( 5 * ( 2 + 6 ) + 10 * ( 3 + 2 ) )
이 경우 가장 외곽의 괄호 안을 보면 여전히 내부에 스택이 존재하고 있습니다.
따라서 스택은 우선 내부에 스택이 없는 부분부터 처리해갑니다. ( 2 + 6 ) 과 ( 3+ 2 ) 는 내부에 스택이 없는 식입니다. 스택은 하나의 값에 수렴할테니 하나의 변수로 대체할 수 있습니다.
변수로 대체할 때의 요령은 단계와 인덱스를 이용해 정리하는 것입니다. 현재 내부에 스택이 하나도 없는 첫단계입니다. (2+6)은 그 첫단계의 0번 인덱스를 갖게 되고 (3+2)는 1번 인덱스를 부여하면 될 것입니다. 이를 간단히 괄호스택으로 표현하는 변수로 대체해보죠.
3 * ( 5 * @paren0_0 + 10 * @paren0_1 )
이 변수명은 @로 시작하므로 자바스크립트의 변수 식별자가 될 수 없는 특수한 구문임을 만족하고 동시에 0번단계의 인덱스 0번과 1번을 잘 표현하고 있습니다.
저 괄호 안을 나중에 처리하려고 미뤘으니 괄호안의 내용을 어딘가는 저장해둬야겠죠. 구조를 담기 위해서는 2차원 배열(단계와 인덱스)이 필요합니다. 간단히 만들어보죠.
var paren = []; paren[0] = []; //0단계 paren[0][0] = "2 + 6"; paren[0][1] = "3 + 2";
이제 변수로 대체하고 미뤄둔 만큼 paren에 처리할 식을 기억하게 해뒀으니 문제 없습니다. 하지만 대체된 식도 여전히 괄호를 갖고 있습니다. 그럼 이를 다시 대체하죠.
이젠 0단계가 아니라 1번째 단계로 한 계단 상승합니다.
3 * @paren1_0
자 이제 최종식이 되었군요. paren에도 원래 식을 기억해둬야합니다.
paren[1] = []; //1단계 paren[1][0] = "5 * @paren0_0 + 10 * @paren0_1";
결국 스택이 있는 식은 스택이 없는 가장 내부에서부터 차근차근 스택이 없어지도록 변수로 대체해가면서 식을 별도의 메모리에 옮겨두고 처리를 미루는 것으로 해소합니다.
최종식에서는 간단한 산술 연산식이 되어 충분히 1 / 3에서 작성한 식처리기로 처리할 수 있습니다.
하지만 문제는 앞 서 만든 식처리기는 @parenX_X 형태를 값으로 바꿀 줄 모른다는 것이겠죠.
스택 변수를 값으로 바꾸는 처리
앞 서 만든 식처리기는 다음과 같은 구조로 되어있습니다.
var ex = function( v ){
//1단계
//v가 하나의 값으로 특정되는 경우 값으로 파싱하여 반환
//2단계
//만약 1단계에 걸리지 않으면 연산식으로 보고 토큰을 나눔
//나눠진 토큰을 연산자 우선순위를 포함한 연산식처리기로 정리하여
//최종 하나의 값을 도출하고 반환
}
@parenX_X의 형태를 받아들일 수 있게 하는건 사실 매우 쉽습니다. 그저 1단계에 정규식만 하나 추가하면 될 일입니다. @parenX_X형태를 인식할 정규식입니다.
var rparen = /^[@]paren[0-9]+_[0-9]+$/
그저 이 정규식을 1단계에 추가해주고 이를 식으로 환원하여 처리하면 될 것입니다…..만..이게 이제부터 더욱 어려운 단계로 진입하게 됩니다 ^^;
우선 실제 코드를 구현해보죠.
var ex = function( v ){
var result, operator, i, j, k;
if( v in literal ) return literal[v];
if( rnum.test(v) ) return parseFloat(v);
if( rstr.test(v) ) return v.substring( 1, v.length - 1 );
if( rvar.test(v) ) return VAR[v];
//여기에 추가하여 처리
if( rparen.test(v) ) return ex( 추출한 식 );
...
이 스택처리기는 위의 다른 기본값처리기와 두가지면에서 매우 다릅니다.
추출한 식을 얻기위한 스택메모리를 알아야 합니다(앞에 등장했던 paren이차원배열!)
그 식을 알아도 다시 ex에게 보내서 값으로 환원해야 합니다.
이 두 가지는 굉장한 변화를 초래합니다. 우선 paren이차원배열을 어떻게 알 수 있을까요? 이것은 함수형태로 구현하는 이상 인자로 받는 수 밖에 없습니다. 따라서 다음과 같이 ex의 시그니쳐가 변경되어야합니다.
var ex = function( v, paren ){
...
}
이렇게 인자로 paren이 전달되면 그 배열을 통해 식을 추출할 수 있을 것입니다. ex에게 다시 보내서 값을 얻으려할때도 이 paren을 다시 전달해줘야합니다. 하나의 식이 재귀적으로 처리되는 경우는 스택을 공유하게 되니까요. 이제 아까의 의사코드를 실제 코드로 바꾸죠.
var ex = function( v, paren ){
var result, operator, i, j, k;
if( v in literal ) return literal[v];
if( rnum.test(v) ) return parseFloat(v);
if( rstr.test(v) ) return v.substring( 1, v.length - 1 );
if( rvar.test(v) ) return VAR[v];
if( rparen.test(v) ){
v = v.substr(6); //@parenX_X에서 X_X만 남기고
v = v.split('_'); // _로 잘라서 단계와 인덱스를 얻음
v = paren[v[0]][v[1]]; ////식을 paren에서 추출함
return ex( v, paren ); //반드시 paren도 같이 전달해야함
}
...
이런 과정을 통해 @parenX_X는 처리가 됩니다.
스택을 생성하는 처리
이미 스택처리기를 통해 생성한 @parenX_X는 처리가 되는데 정작 스택생성기는 없습니다.
스택생성기는 ex함수의 1단계와 2단계 사이에 들어가야합니다. 왜냐면 단순 값이 아니면서 연산식이 처리되기 전에 해소되야하기 때문이죠. 따라서 ex는 1,2,3단계의 공정이 될 것이고 2단계에서 스택을 생성하게 됩니다.
지금 만들어보는 스택은 괄호처리기므로 스택생성기가 발동해야하는 조건을 괄호가 있는가로 처리하면 됩니다.
var ex = function( v, paren ){
//1단계처리
//2단계 스택생성기
if( v.indexOf('(') > -1 ){ //괄호가 있으면 발동!
//스택을 생성하고 값에 수렴시킨다
}
//3단계 연산식처리기
}
이미 스택생성기 자체는 위에서 다 만들어봤습니다. 단지 어떻게 내부에 괄호가 없을때까지 재귀적으로 스택변수로 대체해가야하는가를 다루지 않았을 뿐이죠….^^;
이러한 재귀적인 문자열의 처리는 직접 구현하면 매우 귀찮지만 자바스크립트의 replace메서드 + 정규식 + 처리함수의 조합을 통해 처리하면 엄청 쉽게 됩니다(너무 쉬워서 멍할 정도)
우선 “내부에 괄호가 없는 괄호식”을 인식할 정규식이 필요합니다. 그건 쉽죠.
var rp = /[(][^()]*[)]/g
이 간단한 정규식은 괄호로 시작하고 내부에는 괄호가 없는 – 즉 괄호식을 포함하지 않는 괄호식을 나타냅니다. 그럼 이를 이용해
v를 replace에 실어주고
이 처리를 단순 문자열이 아니라 함수에게 위임하면
정규식이 인식한 문자열을 인자로 보내주고 함수의 반환값으로 대체합니다.
이를 코드로 보면 오히려 쉽습니다.
v = v.replace( rp, function( token ){
//token은 (xxxx) 가 올 것임!
//이 token을 paren에 저장해야함
//반환할 문자열은 아래와 같은 형태임
return '@paren' + depth + '_' + index;
} );
위의 코드만 봐도 즉시 생성된 함수가 부모스코프에서 인식해야할 변수가 적어도 세가지가 있군요. paren배열, depth, index 를 알아야합니다.
이 중 paren은 ex의 인자에서 이미 선언되어있습니다. 단지 괄호스택을 처음 처리하는 입장에서는 인자가 undefined로 들어오는게 당연하고 본인이 그 paren에 배열을 만들어야하는 거죠.
또한 이렇게 replace된 문자열이 다시 v가 됨으로서 한단계씩 괄호가 제거되어가는 것이므로 마지막에 괄호가 없어질때까지 루프를 돌면서 계속 치환해야 마지막에는 하나의 값으로 수렴될 것입니다. 이상의 내용을 포함하여 ex함수의 모양을 잡아 코드를 보죠.
var ex = function( v, paren ){
var result, operator, i, j, k;</span>
//추가로 두개 더 선언
var depth, index;
//1단계 처리들
//2단계
if( v.indexOf('(') > -1 ){
paren = []; //배열초기화
depth = 0; //최초 단계초기화
//더이상 괄호가 없을 때까지
while( rp.test(v) ){
//단계별 인덱스배열 초기화
paren[depth] = [];
//각 단계별로 인덱스를 초기화함
index = 0;
v = v.replace( rp, function( token ){
//paren에 식을 저장해두고
paren[depth][index] = token;
//문자열을 반환하면서 인덱스를 하나 더해준다.
return '@paren' + depth + '_' + (index++);
});
depth++; //단계를 하나 증가시켜준다.
}
}
//3단계 연산식처리
}
위의 구조를 통해 다층 스택을 생성함과 동시에 하나의 스택변수로 대체하여 단일한 값으로 치환된 상태에서 연산식 처리기로 넘어가게 됩니다.
복습차원에서 그 이후를 말씀드리면 연산식처리기는 토크나이징을 하면서 연산자와 값으로 분리하게되고 각 값을 평가할 때 다시 ex를 호출하게 되는데 과거와 달리 이젠 무조건 paren을 넘기는 식으로 개선되어야합니다.
모든 것이 반영된 괄호스택을 처리하는 코드는 다음과 같습니다.
var VAR = {a:3, b:5};
var op = {'+':1,'-':1,'*':2,'/':2};
var opf = {
'+':function(a,b){return a+b;},
'-':function(a,b){return a-b;},
'*':function(a,b){return a*b;},
'/':function(a,b){return a/b;}
};
var literal = {'true':true, 'false':false, 'null':null, 'undefined':undefined};
var rnum = /^[-]?[0-9.]+$/;
var rstr = /^(["][^"]*["]|['][^']*['])$/;
var rvar = /^[A-Za-z$_][A-Za-z$_0-9]*$/;
var rp = /[(][^)]*[)]/g;
var rparen = /^[@]paren[0-9]+_[0-9]+$/;
var ex = function( v, paren ){
var result, operator, i, j, k, depth, index;
if( v in literal ) return literal[v];
if( rnum.test(v) ) return parseFloat(v);
if( rstr.test(v) ) return v.substring( 1, v.length - 1 );
if( rvar.test(v) ) return VAR[v];
if( rparen.test(v) ){
v = v.substr(6).split('_');
return ex( paren[v[0]][v[1]], paren );
}
if( v.indexOf('(') > -1 ){
paren = [], depth = 0;
while( rp.test(v) ){
paren[depth] = [], index = 0;
v = v.replace( rp, function( token ){
paren[depth][index] = token;
return '@paren' + depth + '_' + (index++);
});
depth++;
}
}
for( result = [], i = k = 0, j = v.length ; i < j ; i++ ){
if( op[operator = v.charAt(i)] ){
result[result.length] = ex( v.substring( k, i ),paren );
result[result.length] = operator;
k = i + 1;
}
}
result[result.length] = ex( v.substr(k), paren );
for( i = 2 ; i > 0 ; i-- ){
j = 1;
while( j < result.length ){
operation = result[j];
if( op[operation] == i )
result.splice( j - 1, 3, opf[operation]( result[j-1], result[j+1] ) );
else j += 2;
}
}
return result[0];
};
여태 장황하게 떠들었지만 코드는 별거 없습니다 ^^; 고작 저정도를 추가하면 괄호스택이 처리됩니다.
결론
이제 괄호스택으로 맛을 봤으니 최초에 언급했던 모든 스택처리기와 @xxxX_X 형태를 파싱하는 1단계추가 처리를 쌍으로 해가면 됩니다. paren은 괄호처리만 해도 벅차니 아예 stack으로 바꿔서 다양한 스택을 받아들일 수 있게 하면 좋겠죠( stack = {paren:[], array:[]} 같은 형태로..)
이번시간엔 까탈스런 스택처리를 알아봤습니다. 식처리기 마지막 포스팅에서는 값객체를 사용하는 방법과 할당처리를 살펴보겠습니다.
![[책] 실천적 데이터 모델링 입문 외 2권](https://www.bsidesoft.com/wp-content/themes/gridzone/img/thumb-medium.png)
recent comment