Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 만드는 기본 계산기: 스택을 활용한 괄호 수식 계산

기본적인 산술식의 결과를 계산하는 간단한 계산기를 C++로 만들어 보겠습니다. 이 계산기가 처리할 수식에는 여는 괄호 '('와 닫는 괄호 ')', 더하기(+), 빼기(-) 부호, 그리고 공백이 포함될 수 있습니다.

예를 들어 입력 문자열이 "5 + 2 - 3"이라면 계산 결과는 4가 됩니다.

문제 해결 접근 방법

이 문제는 스택(Stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심은 세 개의 변수를 관리하는 것입니다.

  • ret : 지금까지 누적된 계산 결과
  • sign : 현재 숫자 앞에 붙은 부호 (+1 또는 -1)
  • num : 현재 읽고 있는 숫자 값

여는 괄호 '('를 만나면 현재 상태(ret과 sign)를 스택에 저장하고, 닫는 괄호 ')'를 만나면 저장된 값을 꺼내어 계산을 이어갑니다.

알고리즘 단계

  • ret = 0, sign = 1, num = 0으로 초기화합니다. n은 문자열 s의 길이입니다.
  • 정수를 저장할 스택 st를 하나 선언합니다.
  • i를 0부터 n-1까지 반복하며 각 문자 x = s[i]에 대해 다음을 검사합니다.
    • x가 숫자('0'~'9')라면 → num = num * 10 + (x - '0')으로 자릿수를 누적합니다.
    • x가 '('라면 → ret에 sign * num을 더한 뒤, ret과 sign을 순서대로 스택에 저장하고 ret = 0, sign = 1, num = 0으로 초기화합니다.
    • x가 ')'라면 → 먼저 ret += sign * num으로 마지막 숫자를 반영합니다. 그다음 스택 최상단 값(부호)을 곱한 뒤 pop하고, 다시 최상단 값(이전 결과)을 더한 뒤 pop합니다.
    • x가 '+'라면 → ret += sign * num을 수행한 후 sign = 1, num = 0으로 초기화합니다.
    • x가 '-'라면 → ret += sign * num을 수행한 후 sign = -1, num = 0으로 초기화합니다.
  • 반복이 끝난 후 num이 0이 아니라면, 마지막 숫자를 반영하기 위해 ret += sign * num을 수행합니다.
  • ret을 반환합니다.

동작 원리

'(' 를 만나면 지금까지 계산된 결과와 직전 부호를 스택에 임시 저장하므로, 괄호 안의 식을 하나의 새로운 계산처럼 독립적으로 처리할 수 있습니다. ')' 를 만나면 괄호 내부에서 계산된 결과를 저장해 두었던 부호와 곱하고, 이전 결과와 다시 더함으로써 전체 수식의 계산을 완성하게 됩니다.

예제 코드

아래의 C++ 구현 예시를 통해 실제 동작 과정을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int calculate(string s) {
        int ret = 0;
        int sign = 1;
        int num = 0;
        int n = s.size();
        stack <int> st;
        for(int i = 0; i < n; ++i){
            char x = s[i];
            if(x >= '0' && x <= '9'){
                num *= 10;
                num += (x - '0');
            }
            else if(x == '('){
                ret += (sign * num);
                st.push(ret);
                st.push(sign);
                ret = 0;
                sign = 1;
                num = 0;
            }
            else if(x == ')'){
                ret += (sign * num);
                sign = 1;
                num = 0;
                ret *= st.top();
                st.pop();
                ret += st.top();
                st.pop();
            }
            else if(x == '+'){
                ret += (sign * num);
                sign = 1;
                num = 0;
            }
            else if(x == '-'){
                ret += (sign * num);
                sign = -1;
                num = 0;
            }
        }
        if(num){
            ret += sign * num;
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.calculate("5 + 2 - 3"));
}

입력

"5 + 2 - 3"

출력

4