import java.util.*; import java.util.regex.Matcher; import java.util.regex.Pattern; class EvaluateSymbolExpressions { // Helper Pair class as originally defined, upgraded to String key for robustness static class Pair { String first; String second; public Pair(String first, String second) { this.first = first; this.second = second; } } private Map cache = new HashMap<>(); private Map expressionsMap = new HashMap<>(); /** * Part 1: Evaluates all expressions recursively. * Throws IllegalArgumentException for Unknown Symbols or Circular Dependencies. */ public Map evaluateExpressions(List inputs) { cache.clear(); expressionsMap.clear(); // Populate expression lookups for (Pair pair : inputs) { expressionsMap.put(pair.first, pair.second); } Set visiting = new HashSet<>(); Set visited = new HashSet<>(); for (Pair pair : inputs) { resolveSymbol(pair.first, visiting, visited, false); } return cache; } // Recursive DFS for Dependency Resolution private double resolveSymbol(String symbol, Set visiting, Set visited, boolean ignoreUnknowns) { if (visiting.contains(symbol)) { throw new IllegalStateException("Circular dependency detected at: " + symbol); } if (visited.contains(symbol)) { return cache.getOrDefault(symbol, 0.0); } if (!expressionsMap.containsKey(symbol)) { if (ignoreUnknowns) return 0.0; // In part 2, ignore unknown variables throw new IllegalArgumentException("Unknown symbol: " + symbol); } visiting.add(symbol); List tokens = tokenize(expressionsMap.get(symbol)); List resolvedTokens = new ArrayList<>(); for (String token : tokens) { if (isOperatorOrParenthesis(token) || isNumber(token)) { resolvedTokens.add(token); } else { // It's a symbol dependency, resolve recursively double val = resolveSymbol(token, visiting, visited, ignoreUnknowns); resolvedTokens.add(String.valueOf(val)); } } double finalValue = evaluatePostfix(infixToPostfix(resolvedTokens)); cache.put(symbol, finalValue); visiting.remove(symbol); visited.add(symbol); return finalValue; } // Tokenizer matching numbers, words, or operators private List tokenize(String expr) { Pattern pattern = Pattern.compile("[a-zA-Z0-9\\.]+|[()+*/-]"); Matcher matcher = pattern.matcher(expr); List tokens = new ArrayList<>(); while (matcher.find()) { tokens.add(matcher.group()); } return tokens; } private boolean isNumber(String str) { try { Double.parseDouble(str); return true; } catch (NumberFormatException e) { return false; } } private boolean isOperatorOrParenthesis(String token) { return token.matches("[()+*/-]"); } private int precedence(String op) { if (op.equals("+") || op.equals("-")) return 1; if (op.equals("*") || op.equals("/")) return 2; return -1; } // Shunting-Yard Algorithm to convert Infix to Postfix notation private List infixToPostfix(List tokens) { List output = new ArrayList<>(); Stack stack = new Stack<>(); for (String token : tokens) { if (isNumber(token)) { output.add(token); } else if (token.equals("(")) { stack.push(token); } else if (token.equals(")")) { while (!stack.isEmpty() && !stack.peek().equals("(")) { output.add(stack.pop()); } stack.pop(); } else { // Operator while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(token)) { output.add(stack.pop()); } stack.push(token); } } while (!stack.isEmpty()) { output.add(stack.pop()); } return output; } // Standard Stack Evaluator for Postfix math operations private double evaluatePostfix(List postfix) { Stack stack = new Stack<>(); for (String token : postfix) { if (isNumber(token)) { stack.push(Double.parseDouble(token)); } else { double b = stack.pop(); double a = stack.pop(); switch (token) { case "+": stack.push(a + b); break; case "-": stack.push(a - b); break; case "*": stack.push(a * b); break; case "/": stack.push(a / b); break; } } } return stack.isEmpty() ? 0.0 : stack.pop(); } public static void main(String[] args) { EvaluateSymbolExpressions obj = new EvaluateSymbolExpressions(); List inputs = List.of(new Pair("a", "3"), new Pair("b", "a+2"), new Pair("c", "b*4"), new Pair("d", "c-a")); Map results = obj.evaluateExpressions(inputs); results.forEach((key, value) -> System.out.println(key + " -> " + value)); } }

Quick Overview

Evaluate Symbol Expressions