작은 계산 언어 '거꾸셈'으로 쓴 식 q개가 주어진다.
식에는 0 이상의 정수, 연산자 + - * ^, 괄호 ( )와 빈칸만 나온다.
빈칸은 한 수 안(숫자와 숫자 사이)만 아니면 아무 곳에나 몇 개든 올 수 있고, 계산에는 아무 뜻이 없다.
수 앞에 붙는 부호(-5 같은 것)는 없고, 모든 식은 문법에 맞는다.
모든 계산은 M = 1,000,003으로 나눈 나머지로 하며, 계산 결과는 언제나 0 이상 M 미만의 값으로 둔다.
그래서 a - b가 음수가 되면 M을 더해 0 이상으로 만든다(예: 0-1의 값은 1,000,002).
a ^ b는 a를 b번 곱한 값을 M으로 나눈 나머지이고, 0 ^ 0은 1이다.
이때 b도 오른쪽 식의 값을 이미 M으로 나눈 나머지이다(예: 2^(1000000+5)에서 b는 1,000,005가 아니라 2이므로 값은 4이다).
거꾸셈의 연산자 순위는 보통 수학과 다르다.
가장 먼저 묶이는 것은 ^이고, 다음은 +와 -(같은 순위), 가장 나중은 *이다.
+, -, *는 왼쪽부터 묶고, ^는 오른쪽부터 묶는다.
예를 들어 2*3+4는 2*(3+4) = 14, 10-3-2는 (10-3)-2 = 5, 2^3^2는 2^(3^2) = 512이다.
괄호 안은 언제나 먼저 계산한다.
식마다 값을 한 줄에 하나씩 출력하라.
입력
첫 줄에 q, 다음 q줄에 줄마다 식 하나가 주어진다. 1 ≤ q ≤ 100, 식 한 줄의 길이는 1 이상 2,000 이하, 식에 나오는 정수는 0 이상 1,000,000 이하이다.
출력
q줄, 줄마다 식의 값(0 이상 1,000,002 이하)
예시 1 · stdin
4
2*3+4
10-3-2
2^3^2
0-1
stdout
14
5
512
1000002
예시 2 · stdin
2
( 2 * 3 ) + 4
1000000 * 1000000
stdout
10
9
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
순위가 있는 식은 스택 두 개로 왼쪽부터 한 번에 계산해요: 수 스택과 연산자 스택. 새 연산자가 오면, 스택 맨 위 연산자가 더 먼저 묶여야 하는 동안 꺼내서 계산하고 나서 새 연산자를 넣어요. 이 '더 먼저'가 핵심이에요: 왼쪽부터 묶는 + - *는 순위가 같아도 꺼내고(10-3-2 = 5), 오른쪽부터 묶는 ^는 순위가 더 높을 때만 꺼내요(2^3^2 = 512). 같을 때도 꺼내면 ^가 (2^3)^2 = 64가 돼요. 보통 수학 순위(*가 먼저)를 습관처럼 쓰면 2*3+4가 10이 되는 것도 흔한 실수예요. 괄호는 여는 괄호를 연산자 스택에 넣어 두고, 닫는 괄호에서 여는 괄호가 나올 때까지 꺼내 계산해요 — 순위마다 함수를 두고 재귀로 내려가면 괄호 한 겹마다 함수가 서너 번 겹쳐 불려서, 괄호가 999겹이거나 ^가 1,000개 이어지면 Python의 기본 재귀 한도(1,000)를 넘어 RecursionError가 나요. 언어마다 다른 곳은 두 가지예요. ① 나머지: Python의 %는 늘 0 이상이지만, C·C++·Java·C#·JavaScript·TypeScript·크레이콘의 %는 왼쪽 수의 부호를 따라 (0 - 1) % M이 -1이에요. 그래서 ((a - b) % M + M) % M으로 고치거나 Java는 Math.floorMod(a - b, M)을 써요. ② 곱의 크기: 두 값을 곱하면 10^12 가까이 돼서 32비트 int(약 21억)를 넘어요. C·C++은 long long, Java·C#은 long으로 계산해요. JavaScript·TypeScript·크레이콘의 수는 배정밀도 실수라 2^53(약 9×10^15)까지 정수가 정확해서 10^12는 그대로 곱해도 돼요. 스택은 Python 목록 append/pop, Java ArrayDeque(push/pop/peek), C# Stack<long>, C++ std::stack, C는 배열과 맨 위 자리 변수, JavaScript·TypeScript는 배열 push/pop, 크레이콘은 목록 넣기와 자리빼기(개수 - 1)로 써요. 크레이콘에서 수를 읽을 때는 글자.코드(ch) - 48로 한 자리씩 쌓고, 연산자 순위는 선택 (op) { 경우 "+", "-": … }로 나눠요.
Pythonmain.py · 55 줄
import sysM = 1_000_003# 이 말에서는 + - 가 * 보다 먼저 묶인다. ^ 가 가장 먼저이고 오른쪽부터 묶인다PREC = {"^": 3, "+": 2, "-": 2, "*": 1}def apply(values, op): b = values.pop() a = values.pop() if op == "+": values.append((a + b) % M) elif op == "-": values.append((a - b) % M) # Python의 %는 늘 0 이상이다 elif op == "*": values.append(a * b % M) else: values.append(pow(a, b, M))def evaluate(line): values = [] # 수 스택 ops = [] # 연산자·여는 괄호 스택 i = 0 while i < len(line): ch = line[i] if ch.isdigit(): j = i while j < len(line) and line[j].isdigit(): j += 1 values.append(int(line[i:j])) i = j continue if ch == "(": ops.append(ch) elif ch == ")": while ops[-1] != "(": apply(values, ops.pop()) ops.pop() elif ch in PREC: # 왼쪽부터 묶는 연산자는 같은 순위도 먼저 계산하고, ^ 는 더 높은 순위만 먼저 계산한다 while ops and ops[-1] != "(" and ( PREC[ops[-1]] > PREC[ch] or (PREC[ops[-1]] == PREC[ch] and ch != "^") ): apply(values, ops.pop()) ops.append(ch) i += 1 while ops: apply(values, ops.pop()) return values[0]lines = sys.stdin.read().split("\n")q = int(lines[0])print("\n".join(str(evaluate(lines[1 + k])) for k in range(q)))
JavaScriptmain.js · 61 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const M = 1000003; // 곱해도 M * M ≈ 10^12라 2^53 안이다(Number로 정확)// 이 말에서는 + - 가 * 보다 먼저 묶인다. ^ 가 가장 먼저이고 오른쪽부터 묶인다const PREC = { "^": 3, "+": 2, "-": 2, "*": 1 };function power(a, b) { let result = 1; while (b > 0) { if (b % 2 === 1) result = (result * a) % M; a = (a * a) % M; b = Math.floor(b / 2); } return result;}function apply(values, op) { const b = values.pop(); const a = values.pop(); if (op === "+") values.push((a + b) % M); else if (op === "-") values.push((((a - b) % M) + M) % M); // %는 음수를 남길 수 있다 else if (op === "*") values.push((a * b) % M); else values.push(power(a, b));}function evaluate(line) { const values = []; // 수 스택 const ops = []; // 연산자·여는 괄호 스택 let i = 0; while (i < line.length) { const ch = line[i]; if (ch >= "0" && ch <= "9") { let j = i; while (j < line.length && line[j] >= "0" && line[j] <= "9") j++; values.push(Number(line.slice(i, j))); i = j; continue; } if (ch === "(") ops.push(ch); else if (ch === ")") { while (ops[ops.length - 1] !== "(") apply(values, ops.pop()); ops.pop(); } else if (ch in PREC) { // 왼쪽부터 묶는 연산자는 같은 순위도 먼저 계산하고, ^ 는 더 높은 순위만 먼저 계산한다 while (ops.length > 0) { const top = ops[ops.length - 1]; if (top === "(") break; if (PREC[top] > PREC[ch] || (PREC[top] === PREC[ch] && ch !== "^")) apply(values, ops.pop()); else break; } ops.push(ch); } i++; } while (ops.length > 0) apply(values, ops.pop()); return values[0];}const q = Number(lines[0]);const out = [];for (let k = 1; k <= q; k++) out.push(String(evaluate(lines[k])));console.log(out.join("\n"));
TypeScriptmain.ts · 70 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const M = 1000003; // 곱해도 M * M ≈ 10^12라 2^53 안이다(number로 정확)type Op = "+" | "-" | "*" | "^";// 이 말에서는 + - 가 * 보다 먼저 묶인다. ^ 가 가장 먼저이고 오른쪽부터 묶인다const PREC: Record<Op, number> = { "^": 3, "+": 2, "-": 2, "*": 1 };const isOp = (ch: string): ch is Op => ch in PREC;function power(a: number, b: number): number { let result = 1; while (b > 0) { if (b % 2 === 1) result = (result * a) % M; a = (a * a) % M; b = Math.floor(b / 2); } return result;}function apply(values: number[], op: Op): void { const b = values.pop()!; const a = values.pop()!; if (op === "+") values.push((a + b) % M); else if (op === "-") values.push((((a - b) % M) + M) % M); // %는 음수를 남길 수 있다 else if (op === "*") values.push((a * b) % M); else values.push(power(a, b));}function evaluate(line: string): number { const values: number[] = []; // 수 스택 const ops: (Op | "(")[] = []; // 연산자·여는 괄호 스택 let i = 0; while (i < line.length) { const ch = line[i]; if (ch >= "0" && ch <= "9") { let j = i; while (j < line.length && line[j] >= "0" && line[j] <= "9") j++; values.push(Number(line.slice(i, j))); i = j; continue; } if (ch === "(") ops.push(ch); else if (ch === ")") { let top = ops.pop()!; while (top !== "(") { apply(values, top); top = ops.pop()!; } } else if (isOp(ch)) { // 왼쪽부터 묶는 연산자는 같은 순위도 먼저 계산하고, ^ 는 더 높은 순위만 먼저 계산한다 while (ops.length > 0) { const top = ops[ops.length - 1]; if (top === "(") break; if (PREC[top] > PREC[ch] || (PREC[top] === PREC[ch] && ch !== "^")) { ops.pop(); apply(values, top); } else break; } ops.push(ch); } i++; } while (ops.length > 0) apply(values, ops.pop() as Op); return values[0];}const q = Number(lines[0]);const out: string[] = [];for (let k = 1; k <= q; k++) out.push(String(evaluate(lines[k])));console.log(out.join("\n"));
JavaMain.java · 76 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;public class Main { static final long M = 1_000_003L; // 이 말에서는 + - 가 * 보다 먼저 묶인다. ^ 가 가장 먼저이고 오른쪽부터 묶인다 static int prec(char op) { switch (op) { case '^': return 3; case '+': case '-': return 2; default: return 1; // '*' } } static long power(long a, long b) { long result = 1; while (b > 0) { if (b % 2 == 1) result = result * a % M; a = a * a % M; b /= 2; } return result; } static void apply(ArrayDeque<Long> values, char op) { long b = values.pop(); long a = values.pop(); long r; if (op == '+') r = (a + b) % M; else if (op == '-') r = Math.floorMod(a - b, M); // %는 음수를 남기니 floorMod else if (op == '*') r = a * b % M; // 곱은 10^12까지라 long else r = power(a, b); values.push(r); } static long evaluate(String line) { ArrayDeque<Long> values = new ArrayDeque<>(); // 수 스택 ArrayDeque<Character> ops = new ArrayDeque<>(); // 연산자·여는 괄호 스택 int i = 0; while (i < line.length()) { char ch = line.charAt(i); if (Character.isDigit(ch)) { long x = 0; while (i < line.length() && Character.isDigit(line.charAt(i))) x = x * 10 + (line.charAt(i++) - '0'); values.push(x); continue; } if (ch == '(') { ops.push(ch); } else if (ch == ')') { while (ops.peek() != '(') apply(values, ops.pop()); ops.pop(); } else if ("+-*^".indexOf(ch) >= 0) { // 왼쪽부터 묶는 연산자는 같은 순위도 먼저 계산하고, ^ 는 더 높은 순위만 먼저 계산한다 while (!ops.isEmpty() && ops.peek() != '(' && (prec(ops.peek()) > prec(ch) || (prec(ops.peek()) == prec(ch) && ch != '^'))) apply(values, ops.pop()); ops.push(ch); } i++; } while (!ops.isEmpty()) apply(values, ops.pop()); return values.peek(); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) out.append(evaluate(in.readLine())).append('\n'); System.out.print(out); }}
C#Main.cs · 84 줄
using System;using System.Collections.Generic;using System.Text;class Program{ const long M = 1_000_003; // 이 말에서는 + - 가 * 보다 먼저 묶인다. ^ 가 가장 먼저이고 오른쪽부터 묶인다 static int Prec(char op) => op switch { '^' => 3, '+' or '-' => 2, _ => 1, // '*' }; static long Power(long a, long b) { long result = 1; while (b > 0) { if (b % 2 == 1) result = result * a % M; a = a * a % M; b /= 2; } return result; } static void Apply(Stack<long> values, char op) { long b = values.Pop(); long a = values.Pop(); values.Push(op switch { '+' => (a + b) % M, '-' => ((a - b) % M + M) % M, // C#의 %는 음수를 남긴다 '*' => a * b % M, // 곱은 10^12까지라 long _ => Power(a, b), }); } static long Evaluate(string line) { var values = new Stack<long>(); // 수 스택 var ops = new Stack<char>(); // 연산자·여는 괄호 스택 int i = 0; while (i < line.Length) { char ch = line[i]; if (char.IsDigit(ch)) { long x = 0; while (i < line.Length && char.IsDigit(line[i])) x = x * 10 + (line[i++] - '0'); values.Push(x); continue; } if (ch == '(') ops.Push(ch); else if (ch == ')') { while (ops.Peek() != '(') Apply(values, ops.Pop()); ops.Pop(); } else if ("+-*^".Contains(ch)) { // 왼쪽부터 묶는 연산자는 같은 순위도 먼저 계산하고, ^ 는 더 높은 순위만 먼저 계산한다 while (ops.Count > 0 && ops.Peek() != '(' && (Prec(ops.Peek()) > Prec(ch) || (Prec(ops.Peek()) == Prec(ch) && ch != '^'))) Apply(values, ops.Pop()); ops.Push(ch); } i++; } while (ops.Count > 0) Apply(values, ops.Pop()); return values.Peek(); } static void Main() { int q = int.Parse(Console.ReadLine().Trim()); var out_ = new StringBuilder(); for (int k = 0; k < q; k++) out_.Append(Evaluate(Console.ReadLine())).Append('\n'); Console.Write(out_); }}
C++main.cpp · 78 줄
#include <cctype>#include <iostream>#include <stack>#include <string>constexpr long long M = 1000003;// 이 말에서는 + - 가 * 보다 먼저 묶인다. ^ 가 가장 먼저이고 오른쪽부터 묶인다int prec(char op) { switch (op) { case '^': return 3; case '+': case '-': return 2; default: return 1; // '*' }}long long power(long long a, long long b) { long long result = 1; while (b > 0) { if (b % 2 == 1) result = result * a % M; a = a * a % M; b /= 2; } return result;}void apply(std::stack<long long>& values, char op) { long long b = values.top(); values.pop(); long long a = values.top(); values.pop(); long long r; if (op == '+') r = (a + b) % M; else if (op == '-') r = ((a - b) % M + M) % M; // C++의 %는 음수를 남긴다 else if (op == '*') r = a * b % M; // 곱은 10^12까지라 long long else r = power(a, b); values.push(r);}long long evaluate(const std::string& line) { std::stack<long long> values; // 수 스택 std::stack<char> ops; // 연산자·여는 괄호 스택 std::size_t i = 0; while (i < line.size()) { char ch = line[i]; if (std::isdigit(static_cast<unsigned char>(ch))) { long long x = 0; while (i < line.size() && std::isdigit(static_cast<unsigned char>(line[i]))) x = x * 10 + (line[i++] - '0'); values.push(x); continue; } if (ch == '(') { ops.push(ch); } else if (ch == ')') { while (ops.top() != '(') { apply(values, ops.top()); ops.pop(); } ops.pop(); } else if (ch == '+' || ch == '-' || ch == '*' || ch == '^') { // 왼쪽부터 묶는 연산자는 같은 순위도 먼저 계산하고, ^ 는 더 높은 순위만 먼저 계산한다 while (!ops.empty() && ops.top() != '(' && (prec(ops.top()) > prec(ch) || (prec(ops.top()) == prec(ch) && ch != '^'))) { apply(values, ops.top()); ops.pop(); } ops.push(ch); } i++; } while (!ops.empty()) { apply(values, ops.top()); ops.pop(); } return values.top();}int main() { std::string line; std::getline(std::cin, line); int q = std::stoi(line); for (int k = 0; k < q; k++) { std::getline(std::cin, line); std::cout << evaluate(line) << "\n"; }}
Cmain.c · 78 줄
#include <stdio.h>#include <string.h>#define M 1000003LL#define MAXLEN 2005/* 이 말에서는 + - 가 * 보다 먼저 묶인다. ^ 가 가장 먼저이고 오른쪽부터 묶인다 */static int prec(char op) { if (op == '^') return 3; if (op == '+' || op == '-') return 2; return 1; /* '*' */}static long long power(long long a, long long b) { long long result = 1; while (b > 0) { if (b % 2 == 1) result = result * a % M; a = a * a % M; b /= 2; } return result;}static long long values[MAXLEN]; /* 수 스택: 곱은 10^12까지 커지니 long long */static char ops[MAXLEN]; /* 연산자·여는 괄호 스택 */static int nv, no;static void apply(char op) { long long b = values[--nv]; long long a = values[--nv]; long long r; if (op == '+') r = (a + b) % M; else if (op == '-') r = ((a - b) % M + M) % M; /* C의 %는 음수를 남긴다 */ else if (op == '*') r = a * b % M; else r = power(a, b); values[nv++] = r;}static long long evaluate(const char *line) { nv = no = 0; for (int i = 0; line[i] != '\0';) { char ch = line[i]; if (ch >= '0' && ch <= '9') { long long x = 0; while (line[i] >= '0' && line[i] <= '9') x = x * 10 + (line[i++] - '0'); values[nv++] = x; continue; } if (ch == '(') { ops[no++] = ch; } else if (ch == ')') { while (ops[no - 1] != '(') apply(ops[--no]); no--; } else if (strchr("+-*^", ch) != NULL) { /* 왼쪽부터 묶는 연산자는 같은 순위도 먼저 계산하고, ^ 는 더 높은 순위만 먼저 계산한다 */ while (no > 0 && ops[no - 1] != '(' && (prec(ops[no - 1]) > prec(ch) || (prec(ops[no - 1]) == prec(ch) && ch != '^'))) apply(ops[--no]); ops[no++] = ch; } i++; } while (no > 0) apply(ops[--no]); return values[0];}int main(void) { static char line[MAXLEN + 5]; int q; if (fgets(line, sizeof line, stdin) == NULL) return 0; sscanf(line, "%d", &q); for (int k = 0; k < q; k++) { if (fgets(line, sizeof line, stdin) == NULL) break; line[strcspn(line, "\r\n")] = '\0'; printf("%lld\n", evaluate(line)); } return 0;}
Craykonmain.cray · 135 줄
M = 1000003; // 곱해도 M × M ≈ 10^12라 2^53 안이다// 이 말에서는 + - 가 * 보다 먼저 묶인다. ^ 가 가장 먼저이고 오른쪽부터 묶인다순위(op){ 선택 (op) { 경우 "^": 돌려주기 3; 경우 "+": 경우 "-": 돌려주기 2; 그밖에: 돌려주기 1; }}거듭제곱(a, b){ result = 1; 동안 (b > 0) { 만약 (b % 2 == 1) { result = result * a % M; } a = a * a % M; b = 수학.몫(b, 2); } 돌려주기 result;}// 수 스택 맨 위 두 개를 꺼내 op로 계산하고 결과를 다시 넣는다계산하기(values, op){ b = values[values.개수 - 1]; values.자리빼기(values.개수 - 1); a = values[values.개수 - 1]; values.자리빼기(values.개수 - 1); r = 0; 만약 (op == "+") { r = (a + b) % M; } 아니면 만약 (op == "-") { r = ((a - b) % M + M) % M; // %는 음수를 남길 수 있다 } 아니면 만약 (op == "*") { r = a * b % M; } 아니면 { r = 거듭제곱(a, b); } values.넣기(r);}숫자인가(ch){ 돌려주기 ch >= "0" && ch <= "9";}식계산(line){ values = []; // 수 스택 ops = []; // 연산자·여는 괄호 스택 i = 0; 동안 (i < line.길이) { ch = line[i]; 만약 (숫자인가(ch)) { x = 0; 동안 (i < line.길이 && 숫자인가(line[i])) { x = x * 10 + (글자.코드(line[i]) - 48); i += 1; } values.넣기(x); 건너뛰기; } 만약 (ch == "(") { ops.넣기(ch); } 아니면 만약 (ch == ")") { 동안 (ops[ops.개수 - 1] != "(") { top = ops[ops.개수 - 1]; ops.자리빼기(ops.개수 - 1); 계산하기(values, top); } ops.자리빼기(ops.개수 - 1); } 아니면 만약 (ch == "+" || ch == "-" || ch == "*" || ch == "^") { // 왼쪽부터 묶는 연산자는 같은 순위도 먼저 계산하고, ^ 는 더 높은 순위만 먼저 계산한다 동안 (ops.개수 > 0) { top = ops[ops.개수 - 1]; 만약 (top == "(") { 그만; } 만약 (순위(top) > 순위(ch) || 순위(top) == 순위(ch) && ch != "^") { ops.자리빼기(ops.개수 - 1); 계산하기(values, top); } 아니면 { 그만; } } ops.넣기(ch); } i += 1; } 동안 (ops.개수 > 0) { top = ops[ops.개수 - 1]; ops.자리빼기(ops.개수 - 1); 계산하기(values, top); } 돌려주기 values[0];}q = 콘솔.줄읽기().공백제거().수로변환();반복 (k = 0; k < q; k++){ 콘솔.쓰기(식계산(콘솔.줄읽기()));}