[C++/Win API] 계산기 만들기-핵심 알고리즘 편

기타 코딩 2024. 7. 27. 15:38

군대가기전에 시간날 때 공부해보고자 마음먹었던, RK4, 뉴턴-랩슨법같은 수치해석 알고리즘, 정수론과 RSA 암호화 알고리즘, 수소꼴 원자 모형 미분방정식 풀기 등을 공부해보면서 시간을 보내고 있었다. 그러다가 생각 났던 것이 GUI를 공부하면 만들어 본다는 계산기였다. 이번 글에서는 아래 계산기의 알고리즘에 대해서 살펴보고, 다음 글에서 Windows API를 이용해 GUI를 만들어보도록 하자

Algorithm

계산기 처럼 단순히 버튼만 많이 만들어서 입력한 내용을 화면에 띄우는 것은 Windows API를 사용하더라도 그리 어렵지 않다. 가장 핵심이 되는 것은 문자열로 입력된 수식을 parsing하는 알고리즘이다. 나는 처음부터 괄호와 exp(), sqrt()같은 함수입력까지 고려하여 알고리즘을 생각하였다. 알고리즘은 크게 사람이 하는 것처럼 우선순위가 가장 높은 순서대로 검색한 뒤, queue에 집어넣어서 처리하는 방법과 가장 낮은 우선순위의 연산자부터 찾아서 문제를 분할 정복으로 나눈 뒤stack으로 처리하는 방법이 있을 것이다. 처음에 전자처럼 만드는 것이 짜기가 쉬울 것이라 생각을 하였지만, 만들다보니 처리해야될 예외가 너무 많은지라 후자의 방법을 택하게 되었다. (심지어 전자의 방법으로 만들려고 투자했던 시간보다 짧은 시간에 후자의 방법으로 구현하고 GUI까지 다 완성하였다.)

$$ 3*\exp( 0.5 + 0.25 *2 + exp(2) ) + 3 + ( 2/(4+3) * (1 + 2/(1+1) ) ) $$

위와 같은 문자열이 입력되었다면, 3 뒤에 있는 +가 가장 우선 순위가 낮다는 것을 알 수 있다. 이를 찾기위해선 뒤에서 부터 검색을 하면서(나중에 사람이 계산한느 것과 같은 순서로 계산하려면) 닫힌 괄호수와 열린 괄호의 수가 같을 때 가장 우선 순위가 낮은 연산자를 검색하면 된다.

이런식으로 문제를 분할해나가면 tree의 구조를 갖는 것을 알 수 있다. 그리고 stack을 이용하면 깊이 우선 탐색을 할 수 있는데, 나중에 부모 node로 올라가서 연산을 수행하여야 하니, 2개의 스택이 필요하다. 대신에 함수의 call stack을 이용하여 재귀적으로 작성하면 깊이 우선 탐색과 자식 노드가 계산 완료된 시점에 부모 노드의 계산을 수행할 수 있게된다.

구체적인 parse 과정은 위와 같이 생각하였다.

시간 복잡도 (Time Complexity)

문자열을 분리해가면서 진행하여도 각 트리의 단계별 문자의 비교 횟수 합은 원래 문자열의 길이 $n$으로 유지된다. 다만 +, -를 먼저 검색해보고, *, /와 ^도 검색해보아야 하니( exp같은 함수는 문자열의 처음과 끝만 비교하면 되니 걸리는 시간이 짧다) 단계별로 총 문자의 비교 횟수는 $3n$이 된다. 그러므로 문자열의 비교횟수가 가장 적을 때는 트리의 깊이가 가장 얕을 때로 위와 같이 각 재귀 단계를 거칠 때 마다 문자열의 길이가 반으로 줄어들 때이다. 이경우 트리의 깊이는 $ \log_2 n$이 되므로 최선의 경우 시간 복잡도는 $ \mathcal{O} ( n \log n ) $이 된다.

반대로 최악의 경우는 $1+2+3+4$와 같은 경우로 아래와 같이 트리가 구성되는 경우이다.

각 단계별로 왼쪽에 오는 문자열의 길이가 1씩 감소하니 이경우 트리의 깊이는 $n$이 된다. 따라서 최악의 경우 시간 복잡도는 $ \mathcal{O} (n^2) $이 된다.

*참고로 이론적으로 얻을 수 있는 최선의 경우의 시간 복잡도는 $1+2+3+4$ 처럼 주어져서 문자열을 처음부터 끝까지만 비교하면 바로 결과가 나오는 경우이다. 즉 $ \mathcal{O} (n) $이다.

이 알고리즘은 정렬 알고리즘의 한 종류이기 때문에 다른 정렬 알고리즘과 비교해보면,

알고리즘	최선	최악
quick-sort	$ \mathcal{O} ( n \log n ) $	$ \mathcal{O} (n^2) $
merge-sort	$ \mathcal{O} ( n \log n ) $	$ \mathcal{O} ( n \log n ) $
insert-sort	$ \mathcal{O} (n) $	$ \mathcal{O} (n^2) $

쓸만한 알고리즘이라는 것을 알 수 있다.

C++ 코드 (C++20)

아래와 같이 _base_tree를 만들고 상속 받아서 최대한 코드 복붙을 피해보자. 그리고 자식 노드에 연산 노드가 올지 숫자 노드가 올지 알 수 없기 때문에 공통 분모가 될 클래스가 필요하기도 하다.

#ifndef __CALC_TREE_HPP__
#define __CALC_TREE_HPP__

#include <cmath>

#include <typeinfo>
#include <stdexcept>

#include <string>
#include <format>

namespace Calc {

//binary base tree
class _tree_base {
    protected:
    bool _is_caulated = false;
    double value = 0.0;

    public:
    _tree_base* first;
    _tree_base* second;

    protected:
    void dispose_child() {
        if(first) {delete first; first = nullptr;}
        if(second) {delete second; second = nullptr;}
    }

    public:
    _tree_base(_tree_base* first = nullptr, _tree_base* second = nullptr) : first(first), second(second) {
        //std::cout << "create node" << std::endl;
    }
    virtual ~_tree_base() {
        dispose_child();
        //std::cout << "delete node" << std::endl;
    }

    virtual double get() {
        throw std::runtime_error(std::format("({}) invalid access to method:get", typeid(*this).name()));
        return 0.0;
    }
    inline bool is_caculated() {return _is_caulated;}
};

class num : public _tree_base {
    public:
    num(const double value) : _tree_base(nullptr, nullptr) {
        this->value = value;
        this->_is_caulated = true;
    }

    double get() override {
        return value;
    }
};

//operator node
class _op_node : public _tree_base {
    public:
    virtual double calc()=0;
    
    double get() override {
        if(is_caculated()) return value;
        else               return calc();
    }
};

class add : public _op_node {
    public:
    add() = default;
    add(double first, double second) {
        this->first = new num(first);
        this->second = new num(second);
    };
    double calc();
};

//사칙 연산 노드는 비슷한 내용이라 중략, 전체 코드는 github 참고

class sqrt : public _op_node {
    public:
    sqrt() = default;
    sqrt(double first) {
        this->first = new num(first);
    }
    double calc();
};

class exp : public _op_node {
    public:
    exp() = default;
    exp(double first) {
        this->first = new num(first);
    }
    double calc();
};

class calc_tree : _tree_base {
    private:
    _tree_base* _make_node(std::string str);

    public:
    calc_tree(std::string str);
    double get() {
        return first->get();
    }
};

}
#endif

//calc_tree.cpp
#include "calc_tree.hpp"
using namespace Calc;

double Calc::add::calc() {
    if(!first || !second ) {
        throw std::runtime_error("(Calc::add) first or second is nullptr");
        return 0.0;
    }

    if(!first->is_caculated()) first->get();
    if(!second->is_caculated()) second->get();

    this->value = first->get() + second->get();
    _is_caulated = true;
    dispose_child();
    return this->value;
}

//비슷한 내용이라 생략

그리고 구체적인 parsing 과정은

+ or -, * or /, ^ 순서대로 검색을 한 다음, 모두 못찾은 경우 stod로 숫자로 변환한다.

//calc_tree.cpp
_tree_base *Calc::calc_tree::_make_node(std::string str) {
    Calc::_tree_base* node = nullptr;
    if(*str.rbegin() == ')') {
        // 그냥 괄호 닫힌 경우아니면, exp, sin, cos, tan, ..
        switch(*str.begin()) {
            default:
                throw std::runtime_error("(_make_node) parse error");
                return nullptr;
            
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                break;
            
            case '(':
                str = str.substr(1, str.length()-2);
                return _make_node(str);
            
            case 'e':
                if(str.length() < 6) break;
                if(str.substr(0, 4) == std::string("exp(")) {
                    str = str.substr(4, str.length()-5);
                    node = new Calc::exp();
                    node->first = _make_node(str);
                    return node;
                }
                break;
            
            case 's':
                //is sin()

                //is sqrt()
                if(str.length() < 7) break;
                if(str.substr(0, 5) == std::string("sqrt(")) {
                    str = str.substr(5, str.length()-6);
                    node = new Calc::sqrt();
                    node->first = _make_node(str);
                    return node;
                }
                break;
        }
        
    }

    unsigned int num_op = 0; //the number of open parenthesis
    unsigned int num_cp = 0; //the number of closed parenthesis
    std::string::size_type pos = 0;

    //+,- 찾기
    for(auto iter = str.rbegin(); iter != str.rend(); ++iter) {
        switch(*iter) {
            default:
                continue;
            
            case ')':
                ++num_cp;
                continue;
            
            case '(':
                ++num_op;
                continue;
            
            case '+':
                if(num_op != num_cp) continue;
                node = new Calc::add();
                pos = std::distance(iter, str.rend()) -1;
                node->first = _make_node(str.substr(0, pos));
                node->second = _make_node(str.substr(pos+1));
                return node;
            
            case '-':
                if(num_op != num_cp) continue;
                node = new Calc::sub();
                pos = std::distance(iter, str.rend()) -1;
                node->first = _make_node(str.substr(0, pos));
                node->second = _make_node(str.substr(pos+1));
                return node;
        }
    }

    //*, / 찾기
    num_cp = 0;
    num_op = 0;
    for(auto iter = str.rbegin(); iter != str.rend(); ++iter) {
        switch(*iter) {
            default:
                continue;
            
            case ')':
                ++num_cp;
                continue;
            
            case '(':
                ++num_op;
                continue;
            
            case '*':
                if(num_op != num_cp) continue;
                node = new Calc::mul();
                pos = std::distance(iter, str.rend()) -1;
                node->first = _make_node(str.substr(0, pos));
                node->second = _make_node(str.substr(pos+1));
                return node;
            
            case '/':
                if(num_op != num_cp) continue;
                node = new Calc::div();
                pos = std::distance(iter, str.rend()) -1;
                node->first = _make_node(str.substr(0, pos));
                node->second = _make_node(str.substr(pos+1));
                return node;
        }
    }

    //^ 찾기
    num_cp = 0;
    num_op = 0;
    for(auto iter = str.rbegin(); iter != str.rend(); ++iter) {
        switch(*iter) {
            default:
                continue;
            
            case ')':
                ++num_cp;
                continue;
            
            case '(':
                ++num_op;
                continue;
            
            case '^':
                if(num_op != num_cp) continue;
                node = new Calc::pow();
                pos = std::distance(iter, str.rend()) -1;
                node->first = _make_node(str.substr(0, pos));
                node->second = _make_node(str.substr(pos+1));
                return node;
        }
    }

    //there is no operator -> number
    std::string::size_type n = 0;
    double value = std::stod(str, &n);
    if(str.length() != n) {
        std::string msg = std::format("(_make_node) parse error: unknown symbols '{}' in {}", str.substr(n), str);
        throw std::runtime_error(msg);
        return nullptr;
    }
    else return new Calc::num(value);

}

테스트용 코드

#include <iostream>

#include <conio.h>
#include "core/calc_tree.hpp"

int main() {
    try {
        std::cout << "add test 1+1=";
        auto add = Calc::add(1, 1);
        std::cout << add.get() << std::endl;

        std::cout << "sub test 1-2=";
        Calc::sub sub(1, 2);
        std::cout << sub.get() << std::endl;

        std::cout << "mul test 2*2=";
        Calc::mul mul(2, 2);
        std::cout << mul.get() << std::endl;

        std::cout << "div test 1/2=";
        Calc::div div(1, 2);
        std::cout << div.get() << std::endl;

        std::cout << "pow test 2^3=";
        Calc::pow pow(2, 3);
        std::cout << pow.get() << std::endl;

        std::cout << "sqrt test sqrt(2)=";
        Calc::sqrt sqrt(2);
        std::cout << sqrt.get() << std::endl;

        std::cout << "exp test exp(1)=";
        Calc::exp exp(1);
        std::cout << exp.get() << std::endl;

        std::cout << "2*3+1=";
        Calc::add tree1;
        auto tree2 = new Calc::mul(2, 3);
        tree1.first = tree2;
        tree1.second = new Calc::num(1);
        std::cout << tree1.get() << std::endl;
        
    }
    catch(std::exception& e) {
        std::cerr << e.what() << std::endl;
        _getch();
        return 1;
    }

    try{
        std::cout << "function: exp(5*2+2*(1+2))+1+(1+1)/2=";
        Calc::calc_tree func("exp(5*2+2*(1+2))+1+(1+1)/2");
        std::cout << func.get() << std::endl;

        std::cout << "function2: 3*exp(0.5+0.25*2+exp(2))+3/5-2*(2/(4+3)*(1+2/(1+1)))=";
        Calc::calc_tree func2("3*exp(0.5+0.25*2+exp(2))+3/5-2*(2/(4+3)*(1+2/(1+1)))");
        std::cout << func2.get() << std::endl;

        std::cout << "function3: 3*exp(2*3^2+exp(1+2)/2)+2/3*sqrt(2)=";
        Calc::calc_tree func3("3*exp(2*3^2+exp(1+2)/2)+2/3*sqrt(2)");
        std::cout << func3.get() << std::endl;
    }
    catch(std::exception& e) {
        std::cerr << e.what() << std::endl;
        _getch();
        return 1;
    }

    
    _getch();
}

파이썬으로 계산한 것과 다르지 않다.

sin, cos, tan 같은 함수들까지 다 구현하기는 귀찮은 관계로 적당히 sqrt와 exp 정도만 만들었다. (만드는 방법은 sqrt, exp와 똑같고, parsing 과정에만 코드를 좀 추가하면 된다. )

Github

전체 코드는 여기를 참고하면 된다.

https://github.com/sidreco214/caculator

GitHub - sidreco214/caculator: caculator

caculator. Contribute to sidreco214/caculator development by creating an account on GitHub.

github.com

저작자표시 비영리 동일조건

'기타 코딩' 카테고리의 다른 글

[C++/Win API] 계산기 만들기 - WinAPI과 GUI편 (0)	2024.07.27
[C++] Embedding Python + CMake (0)	2024.03.02
[Python] 파이썬 코드 배포하기 (0)	2024.03.01

ABOUT ME

시드일지 시드일지

Algorithm

시간 복잡도 (Time Complexity)

C++ 코드 (C++20)

Github

'기타 코딩' 카테고리의 다른 글

티스토리툴바

ABOUT ME

Algorithm

시간 복잡도 (Time Complexity)

C++ 코드 (C++20)

Github

'기타 코딩' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바