[자료구조] 수식의 계산

수식

- 피연산자, 연산자, 분리자로 구성

- 수식의 의미를 이해하기 위해 연산의 수행 순서를 파악해야 함

- 계산 순서를 고정하기 위해 각 연산자에 우선순위를 지정해야 함

C++의 연산자 우선순위

식의 표현

- 중위 표기식: A * B / C

- 후위 표기식: A B * C /

- 전위 표기식: / * A B C

 

후위표기식

- 괄호가 불필요

- 연산자 우선순위 불필요

- 계산 과정이 간단(왼쪽에서 오른쪽)

 

중위 표기에서 후위표기 변환 알고리즘

1. 식을 전부 괄호로 묶음
2. 이항 연산자들을 모두 자기 오른쪽 괄호로 이동
3. 괄호를 전부 삭제

 

예시)

1. A/B-C+D*E-A*C
2. ((((A/B)-C)+(D*E))-(A*C))
3. AB/C-DE*+AC*-

이때 피연산자의 순서는 불변

 

A+B*C → ABC*+

다음 토큰	스택	출력
없음	공백	없음
A	공백	A
+	+	A
B	+	AB
*	+*	AB
C	+*	ABC
완료	공백	ABC*+

 

A*(B+C)*D → ABC+*D*

다음 토큰	스택	출력
없음	공백	없음
A	공백	A
*	*	A
(	*(	A
B	*(	AB
+	*(+	AB
C	*(+	ABC
)	*	ABC+
*	*	ABC+*
D	*	ABC+*D
완료	공백	ABC+*D*

 

우선순위를 기반으로 스택킹과 언스택킹을 수행

'(' 괄호 때문에 복잡해짐

• 스택 속에 있을 때는 낮은 우선순위의 연산자처럼 동작
• 그 외의 경우 높은 우선순위의 연산자처럼 동작

해결 방법

• isp(in-stack priority), icp(in-coming priority) 사용
• 연산자는 자신의 isp가 새로운 연산자의 icp보다 산술적으로 작거나 같을 때 스택 밖으로 나옴

 

 

구현

void Postfix(Expression e)
{ // 수식 e를 전달받음
  // 수식 e의 마지막 토큰은 #
    Stack<Token> stack; // 스택 생성
    stack.Push('#');    // 스택의 시작은 #
    for (Token x = NextToken(e); x != '#'; x = NextToken(e))
        if (isdigit(x) || isalpha(x))
        // if 괄호 안쪽은 x가 피연산자(숫자, 알파벳)라면 true, 아니면 false
            cout << x;
        else if (x == ')')
        { // '(' 전까지 스택 배출
            for (; stack.Top() != '('; stack.Pop())
                cout << stack.Top();
            stack.Pop(); // '(' 배출
        }
        else
        { // x는 연산자, 연산자 우선순위를 비교해서 배출
            for (; isp(stack.Top()) <= icp(x); stack.Pop())
                cout << stack.Top();
            stack.Push(x);
        }
        
    // 스택의 남은 부분 전부 배출
    for (; !stack.IsEmpty(); cout << stack.Top(), stack.Pop())
        ;
    cout << endl;
}

 

시간복잡도 - Θ(n)