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

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

 

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

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

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

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

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

1. 피연산자를 만나면 바로 출력

2. 연산자를 만나게 되면 스택에 Push

3. 스택에 보관 중인 연산자 중에서 우선순위가 높은 연산자는 Pop을 하고 출력

4. 스택에 있는 연산자와 외부의 연산자는 우선순위가 다름

5. 닫는 괄호 연산자를 만나게 되면 스택에서 여는 괄호를 만날때 까지 스택에서 Pop을 하고 출력

 

이러한 규칙을 이용하여 중위 표기 수식을 후위 표기 수식으로 변환 할 수 있다.

1. 5는 피연산자 이므로 출력한다.

  - 출력 : 5

2. +는 연산자 이므로 스택에 넣어준다.

 - 출력 : 5

 - 스택 : +

3. 6은 피연산자 이므로 출력한다.

 - 출력 : 56

 - 스택 : +

4. *는 연산자 이므로 스택에 넣어준다. 이때 스택의 최상위 연산자는 +이다. *와 +연산자는 *연산자가 우선순위가 높기때문에 그대로 스택에 넣어준다.

 - 출력 : 56

 - 스택 : +*

5. 2는 피연산자 이므로 출력한다.

 - 출력 : 562

 - 스택 : +*

6. -는 연산자 이므로 스택에 넣어준다. 이때 스택의 최상위 연산자는 *이다. *와 -연산자는 *연산자가 우선위가 높기때문에 *의 연산자 즉 스택에 있는 *연산자는 출력해주고 -연산자는 스택에 넣어준다.

 - 출력 562*

 - 스택 : +-

7. 4는 피연산자 이므로 출력한다.

 - 출력 : 562*4

 - 스택 : +-

8. 더이상 식이 없기 때문에 스택에 존재하는 연산자를 차례대로 출력해준다.

 - 출력 : 562*4-+

 

==스택의 데이터에서 우선순위를 반환해주는 함수==

==스택의 데이터에서 우선순위를 반환해주는 함수==

int GetStackPriority(const char& StackTopData)
{
    switch (StackTopData)
    {
    case '(':
        return 0;
    case ')':
        return 4;
    case '*':
    case '/':
        return 2;
    case '+':
    case '-':
        return 1;
    }
}

==중위 수식의 데이터에서 우선순위를 반환해주는 함수==

int GetInFixPriority(const char& StackTopData)
{
    switch (StackTopData)
    {
    case '(':
        return 5;
    case ')':
        return 4;
    case '*':
    case '/':
        return 2;
    case '+':
    case '-':
        return 1;
    }
}

==중위 수식을 후위 수식으로 바꾸고 반환 해주는 함수==

string GetPostfix(const string& InfixExpression)
{
	int InfixLength = InfixExpression.length();
	
	string PostfixExpression;

    MyStack* Stack = new MyStack();

	for (int i = 0; i < InfixLength; ++i)
	{
		if (InfixExpression[i] == ' ')
		{
			continue;
		}
		char Ch = InfixExpression[i];

		int CheckCh = isdigit(Ch);

		if (CheckCh > 0 || Ch == '.')
		{
			PostfixExpression.append(1, Ch);
		}
		else
		{
            if (!Stack->IsEmpty())
            {
                if (Ch == ')')
                {
                    while (Stack->Top() != '(')
                    {
                        PostfixExpression.append(1, Stack->Pop());
                    }
                    Stack->Pop();
                    continue;
                }

                char StackPopCh = Stack->Top();
                int InFixPriority = GetInFixPriority(Ch);
                int StackPriority = GetStackPriority(StackPopCh);

                if (InFixPriority < StackPriority)
                {
                    PostfixExpression.append(1, Stack->Pop());
                }
            }
            Stack->Push(Ch);
		}
	}

    while (!Stack->IsEmpty())
    {
        PostfixExpression.append(1, Stack->Pop());
    }

	return PostfixExpression;
}