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++){ 控制台.输出(식계산(控制台.读行()));}