[Stack][Hard] 224. Basic Calculator

https://leetcode.com/problems/basic-calculator/description

 

Q. 괄호와 기본 +, - 연산을 지원하는 기본 계산기를 구현하라. 

 

 

 

Solution. 

 단순해 보이지만, 조금 문제에 대해 세부 파악이 필요한 문제다. 

 괄호로 인한 계산 우선 순위, 부호에 의한 값 반전 등 고려해야 할 것들이 있다. 

 

 숫자는 부호를 포함해 한덩어리로 생각하기로 한다. 

 그러면 괄호로 둘러싸인 숫자의 연속이 된다. 

 

 닫는 괄호가 나오면, 열린 괄호를 만날때까지 숫자를 더해 준다. 

 이때 마이너스 값은 음수로 더해 질 것이다. 

 다만, 괄호를 만나 마감하기 전, 한번 더 그 앞 기호를 확인해 음수이면 최종값을 stack에 반영하기 전에 

 다시 음수 전환 해 준다. 

 

 위 로직의 연속. 

 

// stack에 숫자를 쓴다. 여러자리 digit과 음수일 경우를 고려해 push 한다.
void PutNumber(int num, Stack<char> sBuff)
{
    string strNum = "";
    bool neg = num < 0;
    num = Math.Abs(num);
    // Console.WriteLine("putting num : " + num);

    while(num >= 0)
    {
        strNum += (char)(num%10 + '0');
        if(num == 0)    break;
        num /= 10;
    }
    strNum = new string( strNum.Reverse().ToArray() );

    if(neg) sBuff.Push('-');
    for(int z = 0; z < strNum.Length; ++z)
        sBuff.Push(strNum[z]);
}

// stack에서 부호를 감안한 숫자값을 얻어 반환한다.
// 사용한 값들은 pop 한다.
int PopNumber(Stack<char> sBuff)
{
    string ret = "";
    bool positive = true;
    while(sBuff.Count > 0)
    {
        char cur = sBuff.Peek();
        if(cur == '-' || cur == '+')
        {
            sBuff.Pop();
            positive = cur=='+'; 
            break;
        }
        if(cur<'0' || cur>'9')
            break;

        ret += sBuff.Pop();
    }
    if(ret.Length == 0)
        return int.MaxValue;

    ret = new string( ret.Reverse().ToArray() );
    int mul = positive ? 1 : -1;
    return mul * int.Parse(ret);
}


// Main Logic.
// 괄호 단위로 숫자를 얻어 계속 더한다. 
// 괄호를 닫기 전 부호에 한번 더 신경쓴다.
public int Calculate(string s) 
{
    Stack<char> sBuff = new Stack<char>();
    for(int q = 0; q <= s.Length ; ++q)
    {
        char cur = q==s.Length ? 'E' : s[q];
        if(cur=='E' || cur==')')
        {
            if(sBuff.Count > 0)
            {
                int v2 = PopNumber(sBuff);     
                while(sBuff.Count > 0)
                {
                    if(sBuff.Peek()=='(')
                    {
                        sBuff.Pop();
                        if(sBuff.Count>0 && sBuff.Peek()=='-')
                        {
                            v2 *= -1;
                            sBuff.Pop();
                            sBuff.Push('+');
                        }
                        break;
                    }

                    if(sBuff.Peek()=='+' || sBuff.Peek() == '-')
                        sBuff.Pop();
                    else
                    {
                        int v1 = PopNumber(sBuff);
                        v2 = v1 + v2;
                    }
                }
                PutNumber(v2, sBuff);
            }
        }
        else if(cur!=' ')
            sBuff.Push(cur);
    }

    return PopNumber(sBuff);
}

 

 

쉬워 보이는데 생각보다 쉽지 않다. 

 

조금 훈련이 필요한 문제.