You are given symbol definitions in the form name=expression. An expression may contain integer constants, references to previously defined or later defined symbols, and the binary operators +, -, *, and /.
Evaluate the final integer value of every symbol. Return the results in the same order as the input definitions, formatted as "name=value".
If the dependency graph contains a cycle, return a single-element array ["CYCLE"] instead of partial results.
Function Description
Complete the function evaluateExpressionMap in the editor below.
evaluateExpressionMap has the following parameter:
String[] definitions: the symbol definitions ReturnsString[]: evaluated symbol assignments in input order, or["CYCLE"]if a cycle exists.
Constraints
1 ≤ definitions.length ≤ 10⁵- Expressions use integer arithmetic and may reference other symbols.
- Use cycle detection to avoid infinite recursion.
Example 1
Input:
definitions = ["a=1", "b=a+2", "c=b*3"]Output:
["a=1", "b=3", "c=9"]Explanation: Each symbol depends only on earlier evaluated values, so the map resolves cleanly.
Example 2
Input:
definitions = ["a=b+1", "b=a+1"]Output:
["CYCLE"]Explanation: The definitions form a cycle, so the special cycle marker is returned.
解法
把每个定义解析成「名字 → 表达式 token 序列」，然后对每个 name 做带 visiting 集合的 DFS：递归求值变量，求值过程中再次进入同一个 name 就说明有环，立即返回 CYCLE。表达式求值用经典「分两阶段：先处理 *//，再处理 +/-」或调度场算法。时间 O(N·E)，E 是平均表达式长度。
from typing import List
import re
def evaluateExpressionMap(definitions: List[str]) -> List[str]:
defs: dict[str, str] = {}
order: List[str] = []
for d in definitions:
name, expr = d.split("=", 1)
defs[name.strip()] = expr.strip()
order.append(name.strip())
cache: dict[str, int] = {}
visiting: set[str] = set()
has_cycle = [False]
def evaluate(expr: str) -> int:
tokens = re.findall(r"\d+|[A-Za-z_][A-Za-z_0-9]*|[+\-*/()]", expr)
# Shunting-yard to RPN
prec = {"+": 1, "-": 1, "*": 2, "/": 2}
out: List[str] = []
ops: List[str] = []
for t in tokens:
if t.isdigit() or (t[0].isalpha() or t[0] == "_"):
out.append(t)
elif t in prec:
while ops and ops[-1] in prec and prec[ops[-1]] >= prec[t]:
out.append(ops.pop())
ops.append(t)
while ops:
out.append(ops.pop())
stack: List[int] = []
for t in out:
if t in prec:
b = stack.pop(); a = stack.pop()
if t == "+": stack.append(a + b)
elif t == "-": stack.append(a - b)
elif t == "*": stack.append(a * b)
else: stack.append(a // b if a * b >= 0 else -((-a) // b) if a < 0 else a // b)
elif t.isdigit():
stack.append(int(t))
else:
stack.append(resolve(t))
if has_cycle[0]:
return 0
return stack[0]
def resolve(name: str) -> int:
if has_cycle[0]:
return 0
if name in cache:
return cache[name]
if name in visiting:
has_cycle[0] = True
return 0
visiting.add(name)
v = evaluate(defs[name])
visiting.remove(name)
cache[name] = v
return v
results: List[str] = []
for name in order:
v = resolve(name)
if has_cycle[0]:
return ["CYCLE"]
results.append(f"{name}={v}")
return resultsimport java.util.*;
import java.util.regex.*;
class Solution {
private Map<String, String> defs = new HashMap<>();
private Map<String, Integer> cache = new HashMap<>();
private Set<String> visiting = new HashSet<>();
private boolean hasCycle = false;
String[] evaluateExpressionMap(String[] definitions) {
List<String> order = new ArrayList<>();
for (String d : definitions) {
int eq = d.indexOf('=');
String name = d.substring(0, eq).trim();
defs.put(name, d.substring(eq + 1).trim());
order.add(name);
}
List<String> results = new ArrayList<>();
for (String name : order) {
int v = resolve(name);
if (hasCycle) return new String[]{"CYCLE"};
results.add(name + "=" + v);
}
return results.toArray(new String[0]);
}
private int resolve(String name) {
if (hasCycle) return 0;
if (cache.containsKey(name)) return cache.get(name);
if (visiting.contains(name)) { hasCycle = true; return 0; }
visiting.add(name);
int v = evaluate(defs.get(name));
visiting.remove(name);
cache.put(name, v);
return v;
}
private int evaluate(String expr) {
List<String> tokens = new ArrayList<>();
Matcher m = Pattern.compile("\\d+|[A-Za-z_][A-Za-z_0-9]*|[+\\-*/()]").matcher(expr);
while (m.find()) tokens.add(m.group());
Map<String, Integer> prec = Map.of("+", 1, "-", 1, "*", 2, "/", 2);
List<String> out = new ArrayList<>();
Deque<String> ops = new ArrayDeque<>();
for (String t : tokens) {
if (t.matches("\\d+") || Character.isLetter(t.charAt(0)) || t.charAt(0) == '_') out.add(t);
else if (prec.containsKey(t)) {
while (!ops.isEmpty() && prec.containsKey(ops.peek()) && prec.get(ops.peek()) >= prec.get(t)) out.add(ops.pop());
ops.push(t);
}
}
while (!ops.isEmpty()) out.add(ops.pop());
Deque<Integer> stack = new ArrayDeque<>();
for (String t : out) {
if (prec.containsKey(t)) {
int b = stack.pop(), a = stack.pop();
switch (t) {
case "+": stack.push(a + b); break;
case "-": stack.push(a - b); break;
case "*": stack.push(a * b); break;
default: stack.push(a / b);
}
} else if (t.matches("\\d+")) stack.push(Integer.parseInt(t));
else { stack.push(resolve(t)); if (hasCycle) return 0; }
}
return stack.peek();
}
}#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <regex>
class Solution {
std::unordered_map<std::string, std::string> defs;
std::unordered_map<std::string, int> cache;
std::unordered_set<std::string> visiting;
bool hasCycle = false;
int evaluate(const std::string& expr) {
std::vector<std::string> tokens;
std::regex re("\\d+|[A-Za-z_][A-Za-z_0-9]*|[+\\-*/()]");
for (auto it = std::sregex_iterator(expr.begin(), expr.end(), re); it != std::sregex_iterator(); ++it)
tokens.push_back(it->str());
std::unordered_map<std::string, int> prec{{"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}};
std::vector<std::string> out;
std::stack<std::string> ops;
for (auto& t : tokens) {
if (isdigit(t[0]) || isalpha(t[0]) || t[0] == '_') out.push_back(t);
else if (prec.count(t)) {
while (!ops.empty() && prec.count(ops.top()) && prec[ops.top()] >= prec[t]) { out.push_back(ops.top()); ops.pop(); }
ops.push(t);
}
}
while (!ops.empty()) { out.push_back(ops.top()); ops.pop(); }
std::stack<int> st;
for (auto& t : out) {
if (prec.count(t)) {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
if (t == "+") st.push(a + b);
else if (t == "-") st.push(a - b);
else if (t == "*") st.push(a * b);
else st.push(a / b);
} else if (isdigit(t[0])) st.push(std::stoi(t));
else { st.push(resolve(t)); if (hasCycle) return 0; }
}
return st.top();
}
int resolve(const std::string& name) {
if (hasCycle) return 0;
auto it = cache.find(name);
if (it != cache.end()) return it->second;
if (visiting.count(name)) { hasCycle = true; return 0; }
visiting.insert(name);
int v = evaluate(defs[name]);
visiting.erase(name);
cache[name] = v;
return v;
}
public:
std::vector<std::string> evaluateExpressionMap(std::vector<std::string>& definitions) {
std::vector<std::string> order;
for (auto& d : definitions) {
auto eq = d.find('=');
std::string name = d.substr(0, eq);
defs[name] = d.substr(eq + 1);
order.push_back(name);
}
std::vector<std::string> results;
for (auto& name : order) {
int v = resolve(name);
if (hasCycle) return {"CYCLE"};
results.push_back(name + "=" + std::to_string(v));
}
return results;
}
};Complete the function below. The function receives the full standard input as a single string and returns the exact standard output lines for a small spreadsheet engine.
Implement a spreadsheet with cell labels such as A1 and B10. The spreadsheet supports setting cells to integers or formulas, retrieving evaluated values, and detecting cycles.
A formula is a +-separated expression containing non-negative integer literals and/or cell labels. Operators other than + are not required.
Supported commands:
SET label value: setlabelto an integer or formula. ReturnOKif the assignment does not create a dependency cycle; otherwise leave the spreadsheet unchanged and returnERROR.GET label: return the evaluated integer value oflabel. ReturnERRORif the cell is unset or cannot be evaluated. Cell dependencies are evaluated lazily or eagerly as you choose, butGETmust always reflect the latest committed cell values. Function Description CompletesolveSpreadsheetFormulaEvaluator. It has one parameter,String input, containing newline-separated commands. Return the stdout payload as an array of lines, without trailing newline characters.
Constraints
Cell labels consist of uppercase letters followed by digits, such as A1 or B10.
Formula expressions only need to support addition with +.
Assignments that introduce a cycle must be rejected.
解法
用「依赖图」存每个单元格的公式(token 列表)。SET 时先把候选公式临时代入，做一次 DFS 检测环(visiting 灰色集)，无环则正式提交，否则回滚并输出 ERROR。GET 时按需求值：递归把每个 cell ref 解析为整数，公式只支持 +。时间：每次 GET O(依赖大小)；可加缓存。空间 O(单元格数)。
from typing import List
def solveSpreadsheetFormulaEvaluator(input: str) -> List[str]:
formulas: dict[str, list[str]] = {} # label -> tokens
out: List[str] = []
def parse(expr: str) -> list[str]:
return [t.strip() for t in expr.split("+") if t.strip()]
def has_cycle(start: str, candidate: list[str]) -> bool:
# DFS from start using candidate for start, existing formulas otherwise
WHITE, GRAY, BLACK = 0, 1, 2
color: dict[str, int] = {}
def dfs(node: str) -> bool:
if color.get(node, WHITE) == GRAY:
return True
if color.get(node, WHITE) == BLACK:
return False
color[node] = GRAY
tokens = candidate if node == start else formulas.get(node, [])
for tk in tokens:
if not tk.isdigit():
if dfs(tk):
return True
color[node] = BLACK
return False
return dfs(start)
def evaluate(label: str) -> int | None:
if label not in formulas:
return None
cache: dict[str, int | None] = {}
def rec(node: str) -> int | None:
if node in cache:
return cache[node]
if node not in formulas:
cache[node] = None
return None
total = 0
for tk in formulas[node]:
if tk.isdigit():
total += int(tk)
else:
v = rec(tk)
if v is None:
cache[node] = None
return None
total += v
cache[node] = total
return total
return rec(label)
for line in input.strip().split("\n"):
parts = line.split(maxsplit=2)
if parts[0] == "SET":
label = parts[1]
tokens = parse(parts[2])
if has_cycle(label, tokens):
out.append("ERROR")
else:
formulas[label] = tokens
out.append("OK")
else:
v = evaluate(parts[1])
out.append("ERROR" if v is None else str(v))
return outimport java.util.*;
class Solution {
private Map<String, List<String>> formulas = new HashMap<>();
String[] solveSpreadsheetFormulaEvaluator(String input) {
List<String> out = new ArrayList<>();
for (String line : input.strip().split("\n")) {
String[] parts = line.split(" ", 3);
if (parts[0].equals("SET")) {
String label = parts[1];
List<String> tokens = parse(parts[2]);
if (hasCycle(label, tokens)) out.add("ERROR");
else { formulas.put(label, tokens); out.add("OK"); }
} else {
Integer v = evaluate(parts[1], new HashMap<>());
out.add(v == null ? "ERROR" : String.valueOf(v));
}
}
return out.toArray(new String[0]);
}
private List<String> parse(String expr) {
List<String> res = new ArrayList<>();
for (String t : expr.split("\\+")) {
String s = t.trim();
if (!s.isEmpty()) res.add(s);
}
return res;
}
private boolean hasCycle(String start, List<String> candidate) {
Map<String, Integer> color = new HashMap<>();
return dfsCycle(start, start, candidate, color);
}
private boolean dfsCycle(String node, String start, List<String> candidate, Map<String, Integer> color) {
Integer c = color.getOrDefault(node, 0);
if (c == 1) return true;
if (c == 2) return false;
color.put(node, 1);
List<String> tokens = node.equals(start) ? candidate : formulas.getOrDefault(node, Collections.emptyList());
for (String tk : tokens) {
if (!tk.matches("\\d+")) {
if (dfsCycle(tk, start, candidate, color)) return true;
}
}
color.put(node, 2);
return false;
}
private Integer evaluate(String label, Map<String, Integer> cache) {
if (cache.containsKey(label)) return cache.get(label);
if (!formulas.containsKey(label)) { cache.put(label, null); return null; }
int total = 0;
for (String tk : formulas.get(label)) {
if (tk.matches("\\d+")) total += Integer.parseInt(tk);
else {
Integer v = evaluate(tk, cache);
if (v == null) { cache.put(label, null); return null; }
total += v;
}
}
cache.put(label, total);
return total;
}
}#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>
#include <optional>
class Solution {
std::unordered_map<std::string, std::vector<std::string>> formulas;
std::vector<std::string> parse(const std::string& expr) {
std::vector<std::string> res;
std::string cur;
for (char c : expr) {
if (c == '+') {
if (!cur.empty()) { res.push_back(cur); cur.clear(); }
} else if (!isspace((unsigned char) c)) cur.push_back(c);
}
if (!cur.empty()) res.push_back(cur);
return res;
}
bool isNum(const std::string& s) {
for (char c : s) if (!isdigit((unsigned char) c)) return false;
return !s.empty();
}
bool dfsCycle(const std::string& node, const std::string& start, const std::vector<std::string>& cand, std::unordered_map<std::string, int>& color) {
auto it = color.find(node);
if (it != color.end()) { if (it->second == 1) return true; if (it->second == 2) return false; }
color[node] = 1;
const std::vector<std::string>& tokens = (node == start) ? cand : (formulas.count(node) ? formulas[node] : std::vector<std::string>{});
for (auto& tk : tokens) {
if (!isNum(tk)) {
if (dfsCycle(tk, start, cand, color)) return true;
}
}
color[node] = 2;
return false;
}
bool hasCycle(const std::string& start, const std::vector<std::string>& cand) {
std::unordered_map<std::string, int> color;
return dfsCycle(start, start, cand, color);
}
std::optional<int> evaluate(const std::string& label, std::unordered_map<std::string, std::optional<int>>& cache) {
auto it = cache.find(label);
if (it != cache.end()) return it->second;
auto fit = formulas.find(label);
if (fit == formulas.end()) { cache[label] = std::nullopt; return std::nullopt; }
int total = 0;
for (auto& tk : fit->second) {
if (isNum(tk)) total += std::stoi(tk);
else {
auto v = evaluate(tk, cache);
if (!v) { cache[label] = std::nullopt; return std::nullopt; }
total += *v;
}
}
cache[label] = total;
return total;
}
public:
std::vector<std::string> solveSpreadsheetFormulaEvaluator(std::string input) {
std::vector<std::string> out;
std::stringstream ss(input);
std::string line;
while (std::getline(ss, line)) {
if (line.empty()) continue;
std::stringstream ls(line);
std::string cmd, label;
ls >> cmd >> label;
if (cmd == "SET") {
std::string rest;
std::getline(ls, rest);
auto tokens = parse(rest);
if (hasCycle(label, tokens)) out.push_back("ERROR");
else { formulas[label] = tokens; out.push_back("OK"); }
} else {
std::unordered_map<std::string, std::optional<int>> cache;
auto v = evaluate(label, cache);
out.push_back(v ? std::to_string(*v) : "ERROR");
}
}
return out;
}
};