Problem

You are given an algebraic expression in a string format and a map that gives the values to some of the variables in the expression. Your task is to simply the expression by substituting the variables with their values and performing the algebraic operations.

The expression only contains lowercase alphabet variables, integers, addition, subtraction, and multiplication operations, and parentheses. It's guaranteed that there are spaces between different parts of the expression. The result should be presented as a list of strings where each string is a term in the simplified expression.

For example, Input: expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1] Output: ["-1*a","14"]

Here, the value of variable e is given as 1. When substituted we get "1 + 8 - a + 5". This simplifies to "14 - a" which is represented as two terms in the result, "-1*a" and "14".

Approach

The key steps in the solution are as follows.

1. Tokenize the expression. This involves breaking the expression into smaller units such as variables, integers, and operations.

2. Convert the infix expression to postfix for easier evaluation. This is achieved using a Stack. The infix to postfix conversion is based on the precedence of the operators where multiplication comes before addition and subtraction.

3. Evaluate the postfix expression.

4. Simplify the terms and represent them in the required format.

Example

Let's see an example for a better understanding.

Input: expression = "a * b * c + b * a * c * 4", evalvars = [], evalints = []

In this case, we have an expression with multiplication and addition operations. Since there are no evalvars, we aren't substituting any variables.

But the expression can still be simplified by combining like terms. The expression "a * b * c" appears twice. So, it can be combined to "5 * a * b * c".

The final output is ["5ab*c"].

C# Solution

1
2C#
3public class Solution
4{
5    public IList<string> BasicCalculatorIV(string expression, string[] evalvars, int[] evalints)
6    {
7        Dictionary<string, int> dic = new Dictionary<string, int>();
8        for(int i = 0; i < evalvars.Length; i++)
9        {
10            dic.Add(evalvars[i], evalints[i]);
11        }
12        return Calculate(expression, dic, true);
13    }
14    private bool IsLowerCase(string s)
15    {
16        if(s[0] <= '9')
17            return false;
18        return true;
19    }
20    private IList<string> Calculate(string exp, Dictionary<string, int> dic, bool add)
21    {
22        List<string> ans = new List<string>();
23        if(!exp.Contains("(") && !exp.Contains(")"))
24        {
25            string[] str = exp.Split(' ');
26            for(int i = 0; i < str.Length; i += 2)
27            {
28                bool neg = str[i] == "-";
29                bool isLower = IsLowerCase(str[i+1]);
30                if(!add)
31                    neg = !neg;
32                if(!dic.ContainsKey(str[i+1]) || isLower)
33                {
34                    if(neg)
35                        ans.Add("-" + str[i+1]);
36                    else
37                        ans.Add(str[i+1]);
38                }
39                else
40                {
41                    if(neg)
42                        ans.Add("-" + dic[str[i+1]].ToString());
43                    else
44                        ans.Add(dic[str[i+1]].ToString());
45                }
46            }
47            return ans;
48        }
49        int p = 0, start = 0, cnt = 0;
50        for(int i = 0; i < exp.Length; i++)
51        {
52            if(exp[i] == '(')
53            {
54                if(cnt == 0)
55                    start = i;
56                cnt++;
57            }
58            else if(exp[i] == ')')
59            {
60                cnt--;
61                if(cnt == 0)
62                {
63                    string temp = exp.Substring(0, p);
64                    if(i + 1 < exp.Length)
65                        temp += exp.Substring(i+1);
66                    List<string> t1 = Calculate(temp, dic, add);
67                    List<string> t2 = Calculate(exp.Substring(start + 1, i - start - 1), dic, add);
68                    return Merge(t1, t2, exp[p-1] == '+');
69                }
70            }
71            else if(exp[i] != ' ' && cnt == 0)
72            {
73                p = i+1;
74            }
75        }
76        return new List<string>();
77    }
78    private IList<string> Merge(List<string> str1, List<string> str2, bool add)
79    {
80        List<string> ans = new List<string>();
81        for(int i = 0; i < str1.Count; i++)
82        {
83            for(int j = 0; j < str2.Count; j++)
84            {
85                if(add)
86                    ans.Add(str1[i] + "*" + str2[j]);
87                else
88                    ans.Add(str1[i] + "-" + str2[j]);
89            }
90        }
91        return ans;
92    }
93}

Python Solution

1
2python
3class Solution:
4    def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
5        count = collections.Counter(evalvars, evalints)
6        def combine(left, right, symbol):
7            if symbol == '-': right = [-x for x in right]
8            return list(map(int.__add__, left, right))
9        def multiply(left, right):
10            return list(map(int.__mul__, left, right))
11        
12        def calculate(tokens):
13            total = [0]
14            symbols, stack = ['+'], []
15            while tokens:
16                token = tokens.popleft()
17                if token in '+-':
18                    while stack and symbols[-1] == '*':
19                        total = multiply(stack.pop(), total)
20                        symbols.pop()
21                    total = combine(stack.pop() if stack else [0], total, symbols.pop())
22                    symbols.append(token)
23                elif token == '*':
24                    symbols.append(token)
25                elif token in count:
26                    stack.append([count[token]])
27                elif token.isdigit():
28                    stack.append([int(token)])
29                else:
30                    stack.append([0, 1 if token.islower() else 0, int(token.isupper())])
31            while stack:
32                total = combine(stack.pop() if stack else [0], total, symbols.pop())
33            return total
34        return calculate(collections.deque(expression.split()))

Java Solution

1
2java
3package Calculator;
4
5import java.util.*;
6
7public class Solution {
8    HashMap<String, Integer> map;
9    PriorityQueue<String> q;
10
11    public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
12        map = new HashMap<>();
13        for (int i = 0; i < evalvars.length; i++) map.put(evalvars[i], evalints[i]);
14        q = new PriorityQueue<>((a, b) -> (b.split("\\*").length - a.split("\\*").length != 0) ? b.split("\\*").length - a.split("\\*").length : a.compareTo(b));
15        Map<String, Integer> counts = count(expression);
16        for (String c : counts.keySet())
17            if (counts.get(c) != 0) {
18                q.offer(c);
19            }
20        List<String> ans = new ArrayList();
21        while (!q.isEmpty()) {
22            String c = q.poll();
23            ans.add(coefToString(counts.get(c)) + (c.equals("1") ? "" : "*" + c));
24        }
25        return ans;
26    }
27
28    public String coefToString(int x) {
29        return x > 0 ? "+" + x : String.valueOf(x);
30    }
31
32    public Map<String, Integer> combine(Map<String, Integer> counter, int coef, Map<String, Integer> val) {
33        Map<String, Integer> ans = new HashMap();
34        for (String k : counter.keySet()) {
35            for (String v : val.keySet()) {
36                List<String> keys = new ArrayList<>(Arrays.asList((k + "*" + v).split("\\*")));
37                Collections.sort(keys);
38                String key = String.join("*", keys);
39                ans.put(key, ans.getOrDefault(key, 0) + counter.get(k) * val.get(v) * coef);
40            }
41        }
42        return ans;
43    }
44
45    public Map<String, Integer> count(String expr) {
46        Map<String, Integer> ans = new HashMap();
47        boolean prevNum = false;
48        List<String> symbols = new ArrayList<>();
49        symbols.add("+");
50        List<Map<String, Integer>> stack = new ArrayList<>();
51        int i = 0;
52        while (i < expr.length()) {
53            char c = expr.charAt(i);
54            if (c == '(') {
55                if (prevNum) {
56                    stack.add(ans);
57                    symbols.add("*");
58                    ans = new HashMap();
59                    prevNum = false;
60                } else {
61                    stack.add(new HashMap<>());
62                    symbols.add(symbols.remove(symbols.size() - 1));
63                }
64                i++;
65            } else if (c == ')') {
66                Map<String, Integer> temp = ans;
67                ans = stack.remove(stack.size() - 1);
68                String symbol = symbols.remove(symbols.size() - 1);
69                ans = combine(ans, symbol.equals("-") ? -1 : 1, temp);
70                i++;
71                prevNum = true;
72            } else if (c == ' ') {
73                i++;
74            } else if (Character.isLetter(c)) {
75                int j = i;
76                while (j < expr.length() && Character.isLetter(expr.charAt(j))) j++;
77                String var = expr.substring(i, j);
78                i = j;
79                if (map.containsKey(var)) {
80                    ans.put("1", ans.getOrDefault("1", 0) + map.get(var) * (symbols.remove(symbols.size() - 1).equals("-") ? -1 : 1));
81                    prevNum = true;
82                } else {
83                    ans = combine(ans, 1, new HashMap<String, Integer>() {{ put(var, symbols.remove(symbols.size() - 1).equals("-") ? -1 : 1); }});
84                    prevNum = false;
85                }
86            } else if (Character.isDigit(c)) {
87                int j = i;
88                while (j < expr.length() && Character.isDigit(expr.charAt(j))) j++;
89                String num = expr.substring(i, j);
90                i = j;
91                ans.put("1", ans.getOrDefault("1", 0) + Integer.valueOf(num) * (symbols.remove(symbols.size() - 1).equals("-") ? -1 : 1));
92                prevNum = true;
93            } else {
94                symbols.add(c == '+' ? "+" : "-");
95                prevNum = false;
96                i++;
97            }
98        }
99        return ans;
100    }
101}

Javascript Solution

1
2javascript
3var basicCalculatorIV = function(expression, evalvars, evalints) {
4    let HashMap = require("collections/hash-map");
5    let root = new Node();
6    let i = 0;
7    let evalMap = new HashMap();
8
9    for (let i = 0; i < evalvars.length; i++) evalMap.set(evalvars[i], evalints[i]);
10
11    while (i < expression.length) {
12        if(expression.charAt(i) === ' ') {
13            i++;
14            continue;
15        }
16        if(expression.charAt(i) === "+" || expression.charAt(i) === "-") {
17            new Node(root, expression.charAt(i++));
18        } else if(expression.charAt(i) === "(") {
19            let node = new Node(root, "+");
20            root = node;
21            i++;
22        } else if(expression.charAt(i) === ")") {
23            root = root.parent;
24            i++;
25        } else {
26            let j = i;
27            while(j<expression.length && expression.charAt(j)>='a' && expression.charAt(j)<='z') j++;
28            let str = expression.substring(i,j);
29            i=j;
30
31            let num = 1;
32            if(evalMap.has(str)) {
33                num = evalMap.get(str);
34                str = "";
35            }
36
37            if(i<expression.length && expression.charAt(i) === "*") {
38                i++;
39                j=i;
40                while(j<expression.length && expression.charAt(j)>='0' && expression.charAt(j)<='9') j++;
41                num *= parseInt(expression.substring(i,j));
42                i=j;
43            }
44            root.children.get(root.children.size()-1).coe *= root.children.get(root.children.size()-1).term.getOrDefault(str,0)+num;
45            if(str !== "") root.children.get(root.children.size()-1).term.set(str, 1);
46        }
47    }
48
49    let res = new Array(), map = new HashMap();
50    calculate(root, map);
51
52    let keys = Array.from(map.keys());
53
54    keys.sort((a,b)=>(b.length() - a.length() !== 0) ? b.length() - a.length() : a.compareTo(b));
55
56    for(let key of keys) {
57        if(map.get(key) === 0) continue;
58        if(key === "") {
59            res.push(map.get(key) + "");
60        } else {
61            res.push(map.get(key) + "*" + key);
62        }
63    }
64    return res;
65};
66
67calculate = function(root, map) {
68    for(let node of root.children) {
69        if(node.symbol === "*") {
70            let childMap = new HashMap();
71            calculate(node, childMap);
72            let keys = Array.from(childMap.keys());
73            for(let key of keys) {
74                for(let term of key.split("\\*")) {
75                    let val = node.term.getOrDefault(term,0) + childMap.get(key);
76                    if(val === 0) node.term.delete(term);
77                    else node.term.set(term,val);
78                }
79                let res = new Array();
80                let keys = Array.from(node.term.keySet());
81                for(let term of keys) {
82                    for(let i=0;i<node.term.get(term);i++) res.add(term);
83                }
84                res.sort();
85                map.set(String.join("*",res), node.coe);
86            }
87        } else if(node.symbol === "+") {
88            let temp = calculate(node, map);
89            for(let key of temp.keySet()) {
90                let val = map.getOrDefault(key,0) + temp.get(key);
91                if(val === 0) map.delete(key);
92                else map.set(key,val);
93            }
94        } else {
95            let res = new Array(), keys = Array.from(node.term.keySet());
96            for(let term of keys) {
97                for(let i=0;i<node.term.get(term);i++) res.push(term);
98            }
99            res.sort();
100            return new HashMap().set(String.join("*",res), node.coe);
101        }
102    }
103    return map;
104};
105
106class Node {
107    constructor(parent, symbol) {
108        this.parent = parent;
109        if(parent !== undefined) {
110            parent.children.push(this);
111        }
112        this.symbol = symbol;
113        this.term = undefined;
114        this.coe = undefined;
115
116        if(symbol === "*" || symbol === undefined) {
117            this.term = new Map();
118            this.coe = 1;
119        } else {
120            this.coe = 0;
121            this.term = null;
122        }
123
124        this.children = new Array();
125        if(symbol !== undefined) this.children.push(new Node());
126    }
127};

As you can see from the solutions given above, the problem can be solved using a variety of programming languages including C#, Python, Java, and Javascript. Each of these solutions implements the same basic strategy – tokenize the expression, convert the infix expression to postfix for easier evaluation, evaluate the postfix expression and simplify the resulting terms.

In the C# solution, we first prepare a dictionary to map the variable values. Then the expression is divided into fragments based on whether parentheses are present or not. These fragments are further processed depending on whether they contain operations or variables. The Combine and Merge functions are used to combine or merge fragments after calculations have been done on them. The entire process is done recursively till the final simplified form is attained.

The Python solution also uses a similar approach but represents the expression as a deque collection for efficient retrieval and processing.

The Java solution follows a similar approach but employs Hashmaps to store variables and their corresponding integers.

Finally, the Javascript solution, which is slightly more complex, builds a tree-like structure to store and process the variables and operation. The tree nodes represent either an operation or an integer and are processed accordingly.

Despite the difference in syntax and certain functions, the core logic and the approach remains same across all these languages - breaking down the algebraic expression and evaluating it step by step.

Solution Implementation