[JAVA] 자료구조 - 스택(2) : 중위, 후위 표기법

중위 표기 방식 : 연산자가 피연산자 사이에 있는 수식

ex) 2+3*8

 

후위 표기 방식 : 연산자가 피연산자 뒤에 있는 수식

ex) 238*+

 

인간이 주로 사용하는 수식은 중위 표기 방식이며, 컴파일러가 사용하는 수식은 후위 표기 방식이다.

 

후위 표기 방식의 장점은 괄호를 사용하지 않아도 되는 것 이다.

중위 표기 방식 (1+2) * 7은 더하기 연산이 곱셈 연산보다 먼저 수행되어야 하므로 괄호가 필요하지만 

이를 후위 표기 수식으로 나타내면 12+7* 으로 작성이 가능하여 괄호를 사용하지 않고서도 

우선 계산해야 할 내용을 나타낼 수 있다. 또한 연산자의 우선순위도 생각하지 않아도 된다.

 

아래는 후위 표기 수식을 스택을 이용하여 계산하는 과정을 나타낸 그림이다.

 

후위 표기법 연산 순서

 

피연산자(숫자)를 만나면 스택에 push 하고연산자를 만나면 스택에서 피연산자들을 pop 하여

pop한 피연산자들을 연산자로 계산을 한 뒤 다시 스택에 push 해준다.

아래는 후위표기수식 계산 코드이다.

int eval(char exp[])
{
	int op1, op2, value, i = 0; 
    int len = strlen(exp); // len = 수식 문자열의 길이
    char ch;
    StackType s;
    
    init_stack(&s); // 스택 초기화, 구현필요
    for(i = 0; i<len; i++){
    	ch = exp[i];
        if(ch != '+' && ch != '-' && ch != '*' && ch != '/') {
        	value = ch - '0'; // 입력이 피연산자라면
            push(&s, value);
        }
        else {
        	op2 = pop(&s); // 뒤에 삽입된 피연산자부터 pop
            op1 = pop(&s);
    		switch(ch) {
            case '+': push(&s, op1 + op2); break; // 피연산자들을 계산하고 다시 스택에 push
            case '-': push(&s, op1 - op2); break; 
            case '*': push(&s, op1 * op2); break; 
            case '/': push(&s, op1 / op2); break; 
            }
        }
  	}
    return pop(&s);
}

 

중위 표기법과 후위 표기법의 공통점은 피연산자의 순서는 변하지 않는다는 점이나 다만 연산자들의 순서는 달라진다.