You are given q expressions written in a small calculator language called Backcalc.
An expression contains only non-negative integers, the operators + - * ^, parentheses ( ) and spaces.
Any number of spaces may appear anywhere except inside a number, and they mean nothing.
There is no sign in front of a number (nothing like -5), and every expression is well-formed.
All arithmetic is done modulo M = 1,000,003, and every result is kept as a value from 0 to M - 1.
So when a - b would be negative, add M to make it non-negative (for example, 0-1 is 1,000,002).
a ^ b is a multiplied by itself b times, modulo M, and 0 ^ 0 is 1.
Here b is also the value of the right-hand side already taken modulo M (for example, in 2^(1000000+5) b is 2, not 1,000,005, so the value is 4).
Backcalc's operator precedence differs from ordinary math.
^ binds first, then + and - (same level), and * binds last.
+, - and * group from the left, and ^ groups from the right.
For example, 2*3+4 is 2*(3+4) = 14, 10-3-2 is (10-3)-2 = 5, and 2^3^2 is 2^(3^2) = 512.
Whatever is inside parentheses is always computed first.
Print the value of each expression on its own line.
Input
The first line has q, followed by q lines with one expression each. 1 ≤ q ≤ 100, each line is 1 to 2,000 characters long, and every integer in an expression is between 0 and 1,000,000.
Output
q lines, each the value of an expression (0 to 1,000,002)
Example 1 · stdin
4
2*3+4
10-3-2
2^3^2
0-1
stdout
14
5
512
1000002
Example 2 · stdin
2
( 2 * 3 ) + 4
1000000 * 1000000
stdout
10
9
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
An expression with precedence is evaluated left to right in one pass with two stacks: a value stack and an operator stack. When a new operator arrives, keep popping and applying the top operator while it must bind before the new one, then push the new one. That 'before' is the key: the left-grouping + - * pop even on equal precedence (10-3-2 = 5), while the right-grouping ^ pops only on strictly higher precedence (2^3^2 = 512). Popping on equal as well turns ^ into (2^3)^2 = 64. Using ordinary math precedence out of habit (* first), so that 2*3+4 becomes 10, is another common mistake. For parentheses, push the opening one on the operator stack and, at the closing one, pop and apply until the opening one appears — a recursive solution with one function per precedence level nests three or four calls per pair of parentheses, so 999 nested parentheses or a chain of 1,000 ^ goes past Python's default recursion limit (1,000) and raises RecursionError. Two things differ between languages. ① Remainder: Python's % is never negative, but in C, C++, Java, C#, JavaScript, TypeScript and Craykon % follows the sign of the left operand, so (0 - 1) % M is -1. Fix it with ((a - b) % M + M) % M, or in Java use Math.floorMod(a - b, M). ② Size of a product: multiplying two values gives nearly 10^12, beyond a 32-bit int (about 2.1 billion). C and C++ compute in long long, Java and C# in long. JavaScript, TypeScript and Craykon numbers are doubles, exact for integers up to 2^53 (about 9×10^15), so 10^12 can be multiplied directly. The stack is a Python list with append/pop, Java ArrayDeque (push/pop/peek), C# Stack<long>, C++ std::stack, in C an array plus a top index, in JavaScript and TypeScript an array with push/pop, and in Craykon a list with Add and RemoveAt(Count - 1). In Craykon, read a number digit by digit with Str.Code(ch) - 48, and split the precedence with switch (op) { case "+", "-": … }.
Pythonmain.py · 55 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
M = 1000003; // 곱해도 M × M ≈ 10^12라 2^53 안이다// 이 말에서는 + - 가 * 보다 먼저 묶인다. ^ 가 가장 먼저이고 오른쪽부터 묶인다순위(op){ switch (op) { case "^": return 3; case "+": case "-": return 2; default: return 1; }}거듭제곱(a, b){ result = 1; while (b > 0) { if (b % 2 == 1) { result = result * a % M; } a = a * a % M; b = Mathf.Quot(b, 2); } return result;}// 수 스택 맨 위 두 개를 꺼내 op로 계산하고 결과를 다시 넣는다계산하기(values, op){ b = values[values.Count - 1]; values.RemoveAt(values.Count - 1); a = values[values.Count - 1]; values.RemoveAt(values.Count - 1); r = 0; if (op == "+") { r = (a + b) % M; } else if (op == "-") { r = ((a - b) % M + M) % M; // %는 음수를 남길 수 있다 } else if (op == "*") { r = a * b % M; } else { r = 거듭제곱(a, b); } values.Add(r);}숫자인가(ch){ return ch >= "0" && ch <= "9";}식계산(line){ values = []; // 수 스택 ops = []; // 연산자·여는 괄호 스택 i = 0; while (i < line.Length) { ch = line[i]; if (숫자인가(ch)) { x = 0; while (i < line.Length && 숫자인가(line[i])) { x = x * 10 + (Str.Code(line[i]) - 48); i += 1; } values.Add(x); continue; } if (ch == "(") { ops.Add(ch); } else if (ch == ")") { while (ops[ops.Count - 1] != "(") { top = ops[ops.Count - 1]; ops.RemoveAt(ops.Count - 1); 계산하기(values, top); } ops.RemoveAt(ops.Count - 1); } else if (ch == "+" || ch == "-" || ch == "*" || ch == "^") { // 왼쪽부터 묶는 연산자는 같은 순위도 먼저 계산하고, ^ 는 더 높은 순위만 먼저 계산한다 while (ops.Count > 0) { top = ops[ops.Count - 1]; if (top == "(") { break; } if (순위(top) > 순위(ch) || 순위(top) == 순위(ch) && ch != "^") { ops.RemoveAt(ops.Count - 1); 계산하기(values, top); } else { break; } } ops.Add(ch); } i += 1; } while (ops.Count > 0) { top = ops[ops.Count - 1]; ops.RemoveAt(ops.Count - 1); 계산하기(values, top); } return values[0];}q = Console.ReadLine().Trim().ToNumber();for (k = 0; k < q; k++){ Console.WriteLine(식계산(Console.ReadLine()));}