백준 16133번 - 공학용 계산기 (Calculator)

공학용 계산기 (Calculator) (백준 16133번)

개념 : 연산자 우선순위
난이도 :
링크 : https://www.acmicpc.net/problem/16133

---

계산기 문제를 구현했다. 실제 언어 컴파일러도 아마 이런식으로 구현했을 것 같다. 리스트 계산기 문제를 풀기 위해 C++로 구현을 연습했다. python으로는 이미 몇 개월 전에 해결해놓은 상태였다.

알고리즘의 순서는 아래와 같다.

• 숫자와 연산자들을 vector<string>으로 분리
• 연산자 우선순위를 이용하여 후위 연산자 형태로 변환
  • 혹시 잘 모른다면 링크를 참고해보자
• 순서대로 후위 연산

신경써야할 것들이 몇 개 있었다.

• 연산자 우선순위를 설정하는데, 구현상 편의를 위해 (는 0으로 두었다. 알고리즘 상에서 (는 다른 연산자를 꺼내지 않게 된다.
• 후위연산자로 변환할 때, (를 만날 때마다 스택의 empty 포인트를 변경하여, (를 다른 연산자들이 꺼내지 않게 해주었다.
• )를 만나면 (가 나올때까지 스택에서 꺼내어주고 empty 포인트를 이전 empty 포인트로 변경해주었다.
• 연산 순서가 오른쪽부터 진행되는 경우, 스택에서 꺼내줄 때, 자신과 우선순위가 같은 경우에는 빼주지 않고, 계속 쌓아준다.
• 그외 자잘한 WA를 받았는데, 질문 게시판을 통해 해결했다.

1) c++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

unordered_map<string, int> priority;
unordered_map<string, string> right;

void set_priority() {
    priority["("] = 0;
    priority[")"] = 1;
    priority["#"] = 2;
    priority["^"] = 3;
    priority["*"] = 4;
    priority["/"] = 4;
    priority["+"] = 5;
    priority["-"] = 5;
}

void set_right() {
    right["^"] = "^";
    right["#"] = "#";
}

bool is_right(string x) { 
    return right.find(x) != right.end();
}

bool in_priority(string t){
    return priority.find(t) != priority.end();
}

bool in_priority(char x){
    string t(1, x);
    return in_priority(t);
}

ostream& operator<<(ostream &os, vector<string> v) {
    for (auto x : v) cout << x << ' ';
    return os;
}

ostream& operator<<(ostream &os, vector<ll> v) {
    for (auto x : v) cout << x << ' ';
    return os;
}

vector<string> parse_comp(string form){

    vector<string> ret;
    string s;
    for (char x : form) {
        if (in_priority(x)) {
            if (!s.empty()) ret.emplace_back(s);
            ret.emplace_back(1, x);
            s = "";
        } else {
            s += x;
        }
    }
    if (!s.empty()) ret.emplace_back(s);
    return ret;
}

vector<string> parse(vector<string> comp) {
    vector<string> ret;
    vector<string> stack;
    vector<int> empty_point = {-1};

    auto is_stack_empty = [&] () {
        return empty_point.back() == (stack.size() - 1);
    };

    auto push_stack_empty = [&] () { 
        empty_point.push_back(stack.size() - 1);
    };

    auto pop_stack_empty = [&]() {
        empty_point.pop_back();
    };


    for (string c : comp) {
        if (in_priority(c) && priority[c]) {
            if (c == ")") {
                while (!is_stack_empty() && stack.back() != "(") {
                    ret.push_back(stack.back());
                    stack.pop_back();
                }
                stack.pop_back();
                pop_stack_empty();
            } else if (is_right(c)) {
                while (!is_stack_empty() && (!in_priority(stack.back()) || priority[c] > priority[stack.back()])) {
                    ret.push_back(stack.back());
                    stack.pop_back();
                }
                stack.push_back(c);
            } else {
                while (!is_stack_empty() && (!in_priority(stack.back()) || priority[c] >= priority[stack.back()])) {
                    ret.push_back(stack.back());
                    stack.pop_back();
                }
                stack.push_back(c);
            } 
        } else {
            stack.push_back(c);
            if (c == "(") push_stack_empty();
        }
    }
    while (!stack.empty()) {
        ret.push_back(stack.back()); stack.pop_back();
    } 
    return ret;
}

vector<string> preprocess(string form) {
    return parse(parse_comp(form));
}

ll calculate(string form) {
    vector<string> postfix = preprocess(form);
    vector<ll> stack;

    auto get_two_from_stack = [&] () {
        ll a, b;
        a = stack.back();
        stack.pop_back();
        b = stack.back();
        stack.pop_back();
        return pair<ll, ll>(b, a);
    };

    auto get_one_from_stack = [&] () {
        ll a;
        a = stack.back();
        stack.pop_back();
        return a;
    };

    for (string comp : postfix) {
        if (!in_priority(comp)) stack.push_back(stoll(comp));
        else {
            ll a, b;
            if (comp == "+") {
                tie(a, b) = get_two_from_stack();
                stack.push_back(a + b);
            } else if (comp == "-") {
                tie(a, b) = get_two_from_stack();
                stack.push_back(a - b);
            } else if (comp == "*") {
                tie(a, b) = get_two_from_stack();
                stack.push_back(a * b);
            } else if (comp == "/") {
                tie(a, b) = get_two_from_stack();
                stack.push_back(a / b);
            } else if (comp == "^") {
                tie(a, b) = get_two_from_stack();
                stack.push_back(powl(a, b));
            } else if (comp == "#") {
                a = get_one_from_stack();
                stack.push_back(sqrtl(a));
            } else {
                throw 1;
            }
        }
    }
    return stack.back();
}

int main()
{
    set_priority();
    set_right();

    string form;
    cin >> form;
    form.pop_back();
    cout << calculate(form);
} // namespace std;

2) python

from decimal import Decimal
from math import *
v = input()[:-1]

s = []
r = ''
for x in v:
    if '0' <= x <= '9':
        r += x
    else:
        if r:
            s.append(r)
        s.append(x)
        r = ''
if r:
    s.append(r)

op = {'(': 0, ')': 1, '+': 2, '-': 2, '*': 3, '/': 3, '^': 4, '#': 5}
s1 = []
s2 = []
for x in s:
    if x in op:
        if x == '#' or x == '^':
            while s1 and op[s1[-1]] > op[x]:
                s2.append(s1.pop())
        elif x != '(':
            while s1 and op[s1[-1]] >= op[x]:
                s2.append(s1.pop())
            if x == ')':
                s1.pop()
        if x != ')':
            s1.append(x)
    else:
        s2.append(x)
while s1:
    s2.append(s1.pop())


def pow(c, n):
    ret = Decimal(1)
    while n != 0:
        if n % 2 == 1:
            ret *= c
        c *= c
        n //= 2
    return ret


def calculator(opand, opter, op):
    if op == '+':
        return opand + opter
    if op == '-':
        return opand - opter
    if op == '*':
        return opand * opter
    if op == '/':
        return Decimal(int(opand/opter))
    if op == '^':
        return pow(opand, opter)


s = []
for x in s2:
    if x in op:
        if x == '#':
            s.append(Decimal(int(s.pop().sqrt())))
        else:
            opter = s.pop()
            opand = s.pop()
            s.append(calculator(opand, opter, x))
    else:
        s.append(Decimal(x))
print(int(s[0]))