[자료구조] 스택 응용 - 사칙연산 계산기 (2)

스택 응용 - 사칙연산 계산기

 

수식의 중위 표기법, 후위 표기법

스택으로 사칙연산 계산기를 구한하기전 수식에서 중위 표기법과 후위 표기법을 알아야 한다.

중위 표기법은 사람이 알기 쉽게 표현이 가능하고, 후위 표기법은 컴퓨터가 연산을 하기 쉽게 표현한 방법이다.

중위 표기법	후위 표기법
3 + 4 * 8	348*+

후위 표기 수식 -> 중위 표기수식 으로 변환하는 알고리즘

1. 피연산자를 만나면 스택에 Push

2. 연산자를 만나면 연산에 필요한 개수만큼 스택에서 Pop

3. 연산한 결과를 다시 스택에 Push

4. 더이상 없으면 연산 후 출력

======= 위 대한 그림 풀이=======

 

1. 5는 피연산자 이므로 스택에 Push

 - 스택 : 5

2. 6은 피연산자 이므로 스택에 Push

 - 스택 : 5, 6

3. 2는 피연산자 이므로 스택에 Push

 - 스택 : 5, 6, 2

4. *는 연산자 이므로 스택에서 2개를 Pop 후 (2, 6) * 연산

 - 스택 : 5

5.  결과값 ( 6 * 2 )을 다시 스택에 Push

 - 스택 : 5, (6 * 2)

6. 4는 피연산자 이므로 스택에 Push

 - 스택 : 5, (6 * 2), 4

7. -는 연산자 이므로 스택에서 2개를 Pop 후 ( (6 * 2) - 4) * 연산

 - 스택 : 5

8. 결과값 (6 * 2) - 4를 다시 스택에 Push

 - 스택 : 5, (6 * 2) - 4

9. +는 연산자 이므로 스택에서 2개를 Pop 후 ( 5 + (6 * 2) - 4)) * 연산

 - 더이상 검사할 데이터가 없으므로 결과값을 출력

5 + (6 * 2) - 4 = 13

==후위 수식을 중위 수식으로 바꾸고 그 값을 계산해서 반환해주는 함수==

double Calc(const string PostfixExpression)
{
    int Value = -1;

    MyStack* Stack = new MyStack();

    int PostfixLength = PostfixExpression.length();

    for (int i = 0; i < PostfixLength; ++i)
    {
        char Ch = PostfixExpression[i];

        int CheckCh = isdigit(Ch);

        if (CheckCh > 0 || Ch == '.')
        {
            Stack->Push(Ch);
        }
        else
        {
            if (!Stack->IsEmpty())
            {
                int Value1 = (int)Stack->Pop() - 48;
                int Value2 = (int)Stack->Pop() - 48;
                switch (Ch)
                {
                case '+':
                    Value = Value2 + Value1;
                    break;
                case '-':
                    Value = Value2 - Value1;
                    break;
                case '*':
                    Value = Value2 * Value1;
                    break;
                case '/':
                    Value = Value2 / Value1;
                    break;
                }

                Stack->Push(char(Value + 48));
            }
        }
    }

    return Value;
}