public class Solution {
    public IList<string> BasicCalculatorIV(string expression, string[] evalvars, int[] evalints) {
        var vars = new Dictionary<string, int>();

        for (int i = 0; i < evalvars.Length; i++) {
            vars[evalvars[i]] = evalints[i];
        }

        var result = Calculate(expression, vars);

        return ((NodeValuePoly)result).GetList();
    }

    char[][] operationsOrder = new char[][]{
        new char[]{'*', '/'},
        new char[]{'+','-'}
    };

    private NodeValuePoly Calculate(string s, Dictionary<string, int> vars) {
        int charIndex = 0;

        var root = BuildLinkedList(s, ref charIndex);

        return CalculateList(root, vars);
    }

    private NodeValuePoly CalculateList(Node root, Dictionary<string, int> vars) {
        PrintList(root);
        var node = root;

        while (node != null) {
            ResolveNode(node, vars);
            node = node.next;
        }

        foreach (var operations in operationsOrder) {
            PrintList(root);
            node = root;

            while (node.next != null) {
                if (operations.Contains(node.operation)) {
                    ExecuteNode(node);
                } else {
                    node = node.next;
                }
            }
        }

        if (root.next != null) {
            throw new Exception("List must have only 1 value at this point!");
        }
        PrintList(root);

        return (NodeValuePoly)root.GetValue();
    }

    private void PrintList(Node node) {
        while (node != null) {
            Console.Write(" {0}{1} {2}", node.isNegative ? "{-}": "", node.GetValue(), node.operation);
            node = node.next;
        }
        Console.WriteLine();
    }

    void ExecuteNode(Node node) {
        var a = EvaluateNodeValue(node);;
        var b = EvaluateNodeValue(node.next);

        NodeValuePoly c;

        switch (node.operation) {
            case '+':
                c = PolyAdd(a, b, 1);
                break;
            case '-':
                c = PolyAdd(a, b, -1);
                break;
            case '*':
                c = PolyMult(a, b, 1);
                // c = a * b;
                break;
            case '/':
                throw new Exception("/");
                // c = a / b;
                break;
            default:
                throw new Exception("illegal operator");
        }

        node.SetValue(c);
        node.isNegative = false;
        node.operation = node.next.operation;
        node.next = node.next.next;
    }

    private NodeValuePoly PolyAdd(NodeValuePoly a, NodeValuePoly b, int bMultiplier) {
        NodeValuePoly c = new NodeValuePoly();

        foreach (var pair in a.polies) {
            SetDic(c.polies, pair.Key, pair.Value);
        }

        foreach (var pair in b.polies) {
            SetDic(c.polies, pair.Key, GetDic(c.polies, pair.Key) + pair.Value * bMultiplier);
        }

        return c;
    }

    private NodeValuePoly PolyMult(NodeValuePoly a, NodeValuePoly b, int bMultiplier) {
        NodeValuePoly c = new NodeValuePoly();

        foreach (var pairA in a.polies) {
            foreach (var pairB in b.polies) {
                PolyKey key = new PolyKey();

                foreach (var vari in pairA.Key.variables) {
                    SetDic(key.variables, vari.Key, vari.Value);
                }

                foreach (var vari in pairB.Key.variables) {
                    SetDic(key.variables, vari.Key, GetDic(key.variables, vari.Key) + vari.Value * bMultiplier);
                }

                int coef = pairA.Value;
                if (bMultiplier == 1) {
                    coef *= pairB.Value;
                } else {
                    coef /= pairB.Value;
                }

                SetDic(c.polies, key, GetDic(c.polies, key) + coef);
            }
        }

        return c;
    }

    private NodeValuePoly EvaluateNodeValue(Node node) {
        return ((NodeValuePoly)node.GetValue());
    }

    private void ResolveNode(Node node, Dictionary<string, int> vars) {
        var value = node.GetValue();

        // Fixing constants
        if (value is NodeValueVariable) {
            var variable = ((NodeValueVariable)value).variable;

            int valint;

            if (int.TryParse(variable, out valint)) {
                value = new NodeValueInt() {val = valint};
            } else if (vars.ContainsKey(variable)) {
                value = new NodeValueInt() {val = vars[variable]};
            }
        }

        if (value is NodeValueExpression) {
            value = CalculateList(((NodeValueExpression)value).node, vars);
        } else if (value is NodeValueInt) {
            value = new NodeValuePoly((value as NodeValueInt).val);
        } else if (value is NodeValueVariable) {
            value = new NodeValuePoly((value as NodeValueVariable).variable);
        } else {
            throw new Exception("Unsupported expression type");
        }

        /*var valueInt = (NodeValueInt)value;

        if (node.isNegative) {
            valueInt.val = -valueInt.val;
        }
        node.SetValue(valueInt);
        node.isNegative = false;*/

        if  (node.isNegative) {
            throw new Exception("Negative node is not supported");
        }

        node.SetValue(value);
    }

    char[] operations = new char[]{ '+', '-', '*', '/' };

    private Node BuildLinkedList(string s, ref int charIndex) {
        var root = new Node();
        var node = root;

        bool expectSign = true;
        //bool isNegative = false;

        while (charIndex < s.Length) {
            var c = s[charIndex];
            charIndex++;

            if (c == ' ') {
                // noop
            } else if (char.IsDigit(c) || char.IsLetter(c)) {
                if (node.GetValue() == null) {
                    node.SetValue(new NodeValueVariable() { variable = "" });
                }

                var nodeValue = node.GetValue() as NodeValueVariable;

                expectSign = false;
                var digit = c - '0';
                nodeValue.variable = nodeValue.variable + c;
                //if (isNegative) {
                //    nodeValue.val = -nodeValue.val;
                //}
            } else if (operations.Contains(c)) {
                if (expectSign && c == '-') {
                    node.isNegative = true;
                } else {
                    node.operation = c;
                    node.next = new Node();
                    node = node.next;

                    expectSign = true;
                    //isNegative = false;
                }
            } else if (c == '(') {
                expectSign = false;
                var nodeValue = new NodeValueExpression();
                nodeValue.node = BuildLinkedList(s, ref charIndex);
                //nodeValue.val = Calculate(s, ref charIndex);

                //if (isNegative) {
                //    nodeValue.val = -nodeValue.val;
                //}
                node.SetValue(nodeValue);
            } else if (c == ')') {
                break;
            }
        }

        return root;
    }

    class Node {
        public char operation;
        public Node next;

        private NodeValue value;

        public bool isNegative;

        public NodeValue GetValue() {
            return this.value;
        }

        public void SetValue(NodeValue value) {
            this.value = value;
        }
    }

    abstract class NodeValue {

    }

    class NodeValueInt : NodeValue {
        public int val;

        public override string ToString() {
            return val.ToString();
        }
    }

    class NodeValueExpression : NodeValue {
        public Node node;
    }

    class NodeValueVariable : NodeValue {
        public string variable;

        public override string ToString() {
            return variable;
        }
    }

    class NodeValuePoly : NodeValue {
        public Dictionary<PolyKey, int> polies = new Dictionary<PolyKey, int>();

        public NodeValuePoly() {

        }

        public NodeValuePoly(int constant) {
            PolyKey key = new PolyKey();
            SetDic(polies, key, constant);
        }

        public NodeValuePoly(string variable) {
            PolyKey key = new PolyKey();
            SetDic(key.variables, variable, 1);
            SetDic(polies, key, 1);
            Console.WriteLine("XXX " + this.ToString() + " " + this.polies.Count);
        }

        public List<String> GetList() {
            List<string> result = new List<string>();

            foreach (var component in polies.OrderByDescending(p=> p.Key.Power).ThenBy(p=> p.Key.ToString())) {
                result.Add(component.Value.ToString() + component.Key.ToString());
            }

            return result;
        }

        public override String ToString() {
            return String.Join(" | ", GetList());
        }
    }

    class PolyKey {
        public Dictionary<string, int> variables = new Dictionary<string, int>();

        public override bool Equals (object obj) {
            PolyKey other = (PolyKey)obj;

            return this.variables.Count == other.variables.Count && !this.variables.Except(other.variables).Any();
        }

        public override int GetHashCode() {
            HashCode hashCode = new HashCode();

            foreach (var pair in variables.OrderBy(p=> p.Key)) {
                hashCode.Add(pair.Key);
                hashCode.Add(pair.Value);
            }

            return hashCode.ToHashCode();
        }

        public int Power {
            get{
                return variables.Select(p=> p.Value).Sum();
            }
        }

        public override string ToString() {
            StringBuilder sb = new StringBuilder();

            foreach (var pair in variables.OrderBy(v=> v.Key)) {
                for (int i = 0; i < pair.Value; i++) {
                    sb.Append("*");
                    sb.Append(pair.Key);
                }
            }

            return sb.ToString();
        }
    }

    private static void SetDic<TKey>(Dictionary<TKey, int> dic, TKey key, int value) {
        dic[key] = value;

        if (dic[key] == 0) {
            dic.Remove(key);
        }
    }

    private static int GetDic<TKey>(Dictionary<TKey, int> dic, TKey key) {
        if (dic.ContainsKey(key)) {
            return dic[key];
        } else {
            return 0;
        }
    }
}