<p>This morning, I was reading <a href="http://steve.yegge.googlepages.com/when-polymorphism-fails" rel="noreferrer">Steve Yegge's: When Polymorphism Fails</a>, when I came across a question that a co-worker of his used to ask potential employees when they came for their interview at Amazon.</p>

<blockquote>
  <p>As an example of polymorphism in
  action, let's look at the classic
  "eval" interview question, which (as
  far as I know) was brought to Amazon
  by Ron Braunstein. The question is
  quite a rich one, as it manages to
  probe a wide variety of important
  skills: OOP design, recursion, binary
  trees, polymorphism and runtime
  typing, general coding skills, and (if
  you want to make it extra hard)
  parsing theory.</p>
  
  <p>At some point, the candidate hopefully
  realizes that you can represent an
  arithmetic expression as a binary
  tree, assuming you're only using
  binary operators such as "+", "-",
  "*", "/". The leaf nodes are all
  numbers, and the internal nodes are
  all operators. Evaluating the
  expression means walking the tree. If
  the candidate doesn't realize this,
  you can gently lead them to it, or if
  necessary, just tell them.</p>
  
  <p>Even if you tell them, it's still an
  interesting problem.</p>
  
  <p>The first half of the question, which
  some people (whose names I will
  protect to my dying breath, but their
  initials are Willie Lewis) feel is a
  Job Requirement If You Want To Call
  Yourself A Developer And Work At
  Amazon, is actually kinda hard. The
  question is: how do you go from an
  arithmetic expression (e.g. in a
  string) such as "2 + (2)" to an
  expression tree. We may have an ADJ
  challenge on this question at some
  point.</p>
  
  <p>The second half is: let's say this is
  a 2-person project, and your partner,
  who we'll call "Willie", is
  responsible for transforming the
  string expression into a tree. You get
  the easy part: you need to decide what
  classes Willie is to construct the
  tree with. You can do it in any
  language, but make sure you pick one,
  or Willie will hand you assembly
  language. If he's feeling ornery, it
  will be for a processor that is no
  longer manufactured in production.</p>
  
  <p>You'd be amazed at how many candidates
  boff this one.</p>
  
  <p>I won't give away the answer, but a
  Standard Bad Solution involves the use
  of a switch or case statment (or just
  good old-fashioned cascaded-ifs). A
  Slightly Better Solution involves
  using a table of function pointers,
  and the Probably Best Solution
  involves using polymorphism. I
  encourage you to work through it
  sometime. Fun stuff!</p>
</blockquote>

<p>So, let's try to tackle the problem all three ways.  How do you go from an arithmetic expression (e.g. in a string) such as "2 + (2)" to an expression tree using cascaded-if's, a table of function pointers, and/or polymorphism?  </p>

<p>Feel free to tackle one, two, or all three.</p>

<p>[update: title modified to better match what most of the answers have been.]</p>

[{'answer_id': 12538, 'author': 'eplawless', 'author_id': 1370, 'author_profile': 'https://Stackoverflow.com/users/1370', 'pm_score': 2, 'selected': False, 'text': '<p>String Tokenizer + LL(1) Parser will give you an expression tree... the polymorphism way might involve an abstract Arithmetic class with an "evaluate(a,b)" function, which is overridden for each of the operators involved (Addition, Subtraction etc) to return the appropriate value, and the tree contains Integers and Arithmetic operators, which can be evaluated by a post(?)-order traversal of the tree.</p>\n'}, {'answer_id': 12630, 'author': 'Brian Leahy', 'author_id': 580, 'author_profile': 'https://Stackoverflow.com/users/580', 'pm_score': 0, 'selected': False, 'text': '<p>should use a functional language imo.  Trees are harder to represent and manipulate in OO languages.</p>\n'}, {'answer_id': 12655, 'author': 'andrewrk', 'author_id': 432, 'author_profile': 'https://Stackoverflow.com/users/432', 'pm_score': 0, 'selected': False, 'text': '<blockquote>\n  <p>Or maybe this is the real question:\n  how can you represent (2) as a BST?\n  That is the part that is tripping me\n  up.</p>\n</blockquote>\n\n<p>Recursion.</p>\n'}, {'answer_id': 12674, 'author': 'Chris Conway', 'author_id': 1412, 'author_profile': 'https://Stackoverflow.com/users/1412', 'pm_score': 2, 'selected': False, 'text': '<blockquote>\n  <p>The problem, I think, is that we need to parse perentheses, and yet they are not a binary operator? Should we take (2) as a single token, that evaluates to 2?</p>\n</blockquote>\n\n<p>The parens don\'t need to show up in the expression tree, but they do affect its shape. E.g., the tree for (1+2)+3 is different from 1+(2+3):</p>\n\n<pre><code>    +\n   / \\\n  +   3\n / \\\n1   2\n</code></pre>\n\n<p>versus</p>\n\n<pre><code>    +\n   / \\\n  1   +\n     / \\\n    2   3\n</code></pre>\n\n<p>The parentheses are a "hint" to the parser (e.g., per superjoe30, to "recursively descend")</p>\n'}, {'answer_id': 12688, 'author': 'Herms', 'author_id': 1409, 'author_profile': 'https://Stackoverflow.com/users/1409', 'pm_score': 1, 'selected': False, 'text': '<p>Re: Justin</p>\n\n<p>I think the tree would look something like this:</p>\n\n<pre><code>  +\n / \\\n2  ( )\n    |\n    2\n</code></pre>\n\n<p>Basically, you\'d have an "eval" node, that just evaluates the tree below it.  That would then be optimized out to just being:</p>\n\n<pre><code>  +\n / \\\n2   2\n</code></pre>\n\n<p>In this case the parens aren\'t required and don\'t add anything.  They don\'t add anything logically, so they\'d just go away.</p>\n'}, {'answer_id': 12812, 'author': 'eplawless', 'author_id': 1370, 'author_profile': 'https://Stackoverflow.com/users/1370', 'pm_score': 2, 'selected': False, 'text': '<p>This gets into parsing/compiler theory, which is kind of a rabbit hole... <a href="http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools" rel="nofollow noreferrer">The Dragon Book</a> is the standard text for compiler construction, and takes this to extremes. In this particular case, you want to construct a <a href="http://en.wikipedia.org/wiki/Context-free_grammar#Example_3" rel="nofollow noreferrer">context-free grammar</a> for basic arithmetic, then use that grammar to parse out an <a href="http://en.wikipedia.org/wiki/Abstract_syntax_tree" rel="nofollow noreferrer">abstract syntax tree</a>. You can then iterate over the tree, reducing it from the bottom up (it\'s at this point you\'d apply the polymorphism/function pointers/switch statement to reduce the tree).</p>\n\n<p>I\'ve found <a href="http://cg.scs.carleton.ca/~morin/teaching/3002/#notes" rel="nofollow noreferrer">these notes</a> to be incredibly helpful in compiler and parsing theory.</p>\n'}, {'answer_id': 12861, 'author': 'Mark Harrison', 'author_id': 116, 'author_profile': 'https://Stackoverflow.com/users/116', 'pm_score': 5, 'selected': True, 'text': '<p><strong>Polymorphic Tree Walking</strong>, Python version</p>\n\n<pre><code>#!/usr/bin/python\n\nclass Node:\n    """base class, you should not process one of these"""\n    def process(self):\n        raise(\'you should not be processing a node\')\n\nclass BinaryNode(Node):\n    """base class for binary nodes"""\n    def __init__(self, _left, _right):\n        self.left = _left\n        self.right = _right\n    def process(self):\n        raise(\'you should not be processing a binarynode\')\n\nclass Plus(BinaryNode):\n    def process(self):\n        return self.left.process() + self.right.process()\n\nclass Minus(BinaryNode):\n    def process(self):\n        return self.left.process() - self.right.process()\n\nclass Mul(BinaryNode):\n    def process(self):\n        return self.left.process() * self.right.process()\n\nclass Div(BinaryNode):\n    def process(self):\n        return self.left.process() / self.right.process()\n\nclass Num(Node):\n    def __init__(self, _value):\n        self.value = _value\n    def process(self):\n        return self.value\n\ndef demo(n):\n    print n.process()\n\ndemo(Num(2))                                       # 2\ndemo(Plus(Num(2),Num(5)))                          # 2 + 3\ndemo(Plus(Mul(Num(2),Num(3)),Div(Num(10),Num(5)))) # (2 * 3) + (10 / 2)\n</code></pre>\n\n<p>The tests are just building up the binary trees by using constructors.</p>\n\n<p>program structure:</p>\n\n<p>abstract base class: Node</p>\n\n<ul>\n<li>all Nodes inherit from this class</li>\n</ul>\n\n<p>abstract base class: BinaryNode</p>\n\n<ul>\n<li>all binary operators inherit from this class</li>\n<li>process method does the work of evaluting the expression and returning the result</li>\n</ul>\n\n<p>binary operator classes: Plus,Minus,Mul,Div</p>\n\n<ul>\n<li>two child nodes, one each for left side and right side subexpressions</li>\n</ul>\n\n<p>number class: Num</p>\n\n<ul>\n<li>holds a leaf-node numeric value, e.g. 17 or 42</li>\n</ul>\n'}, {'answer_id': 12876, 'author': 'Mark Harrison', 'author_id': 116, 'author_profile': 'https://Stackoverflow.com/users/116', 'pm_score': 0, 'selected': False, 'text': '<p>@Justin:</p>\n\n<p>Look at my note on representing the nodes.  If you use that scheme, then</p>\n\n<pre><code>2 + (2)\n</code></pre>\n\n<p>can be represented as</p>\n\n<pre><code>           .\n          / \\\n         2  ( )\n             |\n             2\n</code></pre>\n'}, {'answer_id': 12893, 'author': 'Mark Harrison', 'author_id': 116, 'author_profile': 'https://Stackoverflow.com/users/116', 'pm_score': 2, 'selected': False, 'text': '<p>Representing the Nodes</p>\n\n<p>If we want to include parentheses, we need 5 kinds of nodes:</p>\n\n<ul>\n<li><p>the binary nodes: Add Minus Mul Div<br>these have two children, a left and right side</p>\n\n<pre><code>     +\n    / \\\nnode   node\n</code></pre></li>\n<li><p>a node to hold a value: Val<br>no children nodes, just a numeric value</p></li>\n<li><p>a node to keep track of the parens: Paren<br>a single child node for the subexpression</p>\n\n<pre><code>    ( )\n     |\n    node\n</code></pre></li>\n</ul>\n\n<p>For a polymorphic solution, we need to have this kind of class relationship:</p>\n\n<ul>\n<li>Node</li>\n<li>BinaryNode : inherit from Node</li>\n<li>Plus : inherit from Binary Node</li>\n<li>Minus : inherit from Binary Node</li>\n<li>Mul : inherit from Binary Node</li>\n<li>Div : inherit from Binary Node</li>\n<li>Value : inherit from Node</li>\n<li>Paren : inherit from node</li>\n</ul>\n\n<p>There is a virtual function for all nodes called eval().  If you call that function, it will return the value of that subexpression.</p>\n'}, {'answer_id': 13643, 'author': 'Pete Kirkham', 'author_id': 1527, 'author_profile': 'https://Stackoverflow.com/users/1527', 'pm_score': 2, 'selected': False, 'text': '<blockquote>\n  <p>I won\'t give away the answer, but a\n  Standard Bad Solution involves the use\n  of a switch or case statment (or just\n  good old-fashioned cascaded-ifs). A\n  Slightly Better Solution involves\n  using a table of function pointers,\n  and the Probably Best Solution\n  involves using polymorphism. </p>\n</blockquote>\n\n<p>The last twenty years of evolution in interpreters can be seen as going the other way - polymorphism (eg naive Smalltalk metacircular interpreters) to function pointers (naive lisp implementations, threaded code, C++) to switch (naive byte code interpreters), and then onwards to JITs and so on - which either require very big classes, or (in singly polymorphic languages) double-dispatch, which reduces the polymorphism to a type-case, and you\'re back at stage one. What definition of \'best\' is in use here?</p>\n\n<p>For simple stuff a polymorphic solution is OK - <a href="http://www.tincancamera.com/examples/java/expressions/ExpressionParser.java.txt" rel="nofollow noreferrer">here\'s one I made earlier</a>, but either stack and bytecode/switch or exploiting the runtime\'s compiler is usually better if you\'re, say, plotting a function with a few thousand data points.</p>\n'}, {'answer_id': 20499, 'author': 'Mat Noguchi', 'author_id': 1799, 'author_profile': 'https://Stackoverflow.com/users/1799', 'pm_score': 1, 'selected': False, 'text': '<p>I think the question is about how to write a parser, not the evaluator. Or rather, how to create the expression tree from a string.</p>\n\n<p>Case statements that return a base class don\'t exactly count.</p>\n\n<p>The basic structure of a "polymorphic" solution (which is another way of saying, I don\'t care what you build this with, I just want to extend it with rewriting the least amount of code possible) is deserializing an object hierarchy from a stream with a (dynamic) set of known types.</p>\n\n<p>The crux of the implementation of the polymorphic solution is to have a way to create an expression object from a pattern matcher, likely recursive. I.e., map a BNF or similar syntax to an object factory.</p>\n'}, {'answer_id': 26225, 'author': 'FreeMemory', 'author_id': 2132, 'author_profile': 'https://Stackoverflow.com/users/2132', 'pm_score': 0, 'selected': False, 'text': '<p>As people have been mentioning previously, when you use expression trees parens are not necessary. The order of operations becomes trivial and obvious when you\'re looking at an expression tree. The parens are hints to the parser.</p>\n\n<p>While the accepted answer is the solution to one half of the problem, the other half - actually parsing the expression - is still unsolved. Typically, these sorts of problems can be solved using a <a href="http://en.wikipedia.org/wiki/Recursive_descent_parser" rel="nofollow noreferrer">recursive descent parser</a>. Writing such a parser is often a fun exercise, but most <a href="http://www.antlr.org/" rel="nofollow noreferrer">modern tools for language parsing</a> will abstract that away for you. </p>\n\n<p>The parser is also <strong>significantly</strong> harder if you allow floating point numbers in your string. I had to create a DFA to accept floating point numbers in C -- it was a very painstaking and detailed task. Remember, valid floating points include: 10, 10., 10.123, 9.876e-5, 1.0f, .025, etc. I assume some dispensation from this (in favor of simplicty and brevity) was made in the interview.</p>\n'}, {'answer_id': 277786, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 2, 'selected': False, 'text': "<p>Hm... I don't think you can write a top-down parser for this without backtracking, so it has to be some sort of a shift-reduce parser. LR(1) or even LALR will of course work just fine with the following (ad-hoc) language definition:</p>\n\n<p>Start -> E1 <br>\nE1 -> E1+E1 | E1-E1 <br>\nE1 -> E2*E2 | E2/E2 | E2 <br>\nE2 -> <em>number</em> | (E1)</p>\n\n<p>Separating it out into E1 and E2 is necessary to maintain the precedence of * and / over + and -.</p>\n\n<p>But this is how I would do it if I had to write the parser by hand:</p>\n\n<ul>\n<li>Two stacks, one storing nodes of the tree as operands and one storing operators</li>\n<li>Read the input left to right, make leaf nodes of the numbers and push them into the operand stack.</li>\n<li>If you have >= 2 operands on the stack, pop 2, combine them with the topmost operator in the operator stack and push this structure back to the operand tree, <em>unless</em></li>\n<li>The next operator has higher precedence that the one currently on top of the stack.</li>\n</ul>\n\n<p>This leaves us the problem of handling brackets. One elegant (I thought) solution is to store the precedence of each operator as a number in a variable. So initially, </p>\n\n<ul>\n<li>int plus, minus = 1;</li>\n<li>int mul, div = 2;</li>\n</ul>\n\n<p>Now every time you see a a left bracket increment all these variables by 2, and every time you see a right bracket, decrement all the variables by 2.</p>\n\n<p>This will ensure that the + in 3*(4+5) has higher precedence than the *, and 3*4 will not be pushed onto the stack. Instead it will wait for 5, push 4+5, then push 3*(4+5).</p>\n"}, {'answer_id': 307536, 'author': 'xxxxxxx', 'author_id': 34051, 'author_profile': 'https://Stackoverflow.com/users/34051', 'pm_score': 0, 'selected': False, 'text': '<p>I\'ve written such a parser with some basic techniques like \n<a href="http://en.wikipedia.org/wiki/Reverse_Polish_notation" rel="nofollow noreferrer">Infix -> RPN</a> and \n<a href="http://en.wikipedia.org/wiki/Shunting_yard_algorithm" rel="nofollow noreferrer">Shunting Yard</a> and \n<a href="http://en.wikipedia.org/wiki/Tree_traversal" rel="nofollow noreferrer">Tree Traversals</a>.\n<a href="http://perlhobby.googlecode.com/svn/trunk/parser_v0.1/" rel="nofollow noreferrer">Here is the implementation I\'ve came up with</a>.<br>\nIt\'s written in C++ and compiles on both Linux and Windows.<br>\nAny suggestions/questions are welcomed.</p>\n\n<blockquote>\n  <p>So, let\'s try to tackle the problem all three ways. How do you go from an arithmetic  expression (e.g. in a string) such as "2 + (2)" to an expression tree using cascaded-if\'s, a table of function pointers, and/or polymorphism? </p>\n</blockquote>\n\n<p>This is interesting,but I don\'t think this belongs to the realm of object-oriented programming...I think it has more to do with <a href="ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf" rel="nofollow noreferrer">parsing techniques</a>.</p>\n'}, {'answer_id': 474783, 'author': 'Wilfred Knievel', 'author_id': 6124, 'author_profile': 'https://Stackoverflow.com/users/6124', 'pm_score': 0, 'selected': False, 'text': '<p>I\'ve kind of chucked this c# console app together as a bit of a proof of concept.  Have a feeling it could be a lot better (that switch statement in GetNode is kind of clunky (it\'s there coz I hit a blank trying to map a class name to an operator)).  Any suggestions on how it could be improved very welcome.</p>\n\n<pre><code>using System;\n\nclass Program\n{\n    static void Main(string[] args)\n    {\n        string expression = "(((3.5 * 4.5) / (1 + 2)) + 5)";\n        Console.WriteLine(string.Format("{0} = {1}", expression, new Expression.ExpressionTree(expression).Value));\n        Console.WriteLine("\\nShow\'s over folks, press a key to exit");\n        Console.ReadKey(false);\n    }\n}\n\nnamespace Expression\n{\n    // -------------------------------------------------------\n\n    abstract class NodeBase\n    {\n        public abstract double Value { get; }\n    }\n\n    // -------------------------------------------------------\n\n    class ValueNode : NodeBase\n    {\n        public ValueNode(double value)\n        {\n            _double = value;\n        }\n\n        private double _double;\n        public override double Value\n        {\n            get\n            {\n                return _double;\n            }\n        }\n    }\n\n    // -------------------------------------------------------\n\n    abstract class ExpressionNodeBase : NodeBase\n    {\n        protected NodeBase GetNode(string expression)\n        {\n            // Remove parenthesis\n            expression = RemoveParenthesis(expression);\n\n            // Is expression just a number?\n            double value = 0;\n            if (double.TryParse(expression, out value))\n            {\n                return new ValueNode(value);\n            }\n            else\n            {\n                int pos = ParseExpression(expression);\n                if (pos &gt; 0)\n                {\n                    string leftExpression = expression.Substring(0, pos - 1).Trim();\n                    string rightExpression = expression.Substring(pos).Trim();\n\n                    switch (expression.Substring(pos - 1, 1))\n                    {\n                        case "+":\n                            return new Add(leftExpression, rightExpression);\n                        case "-":\n                            return new Subtract(leftExpression, rightExpression);\n                        case "*":\n                            return new Multiply(leftExpression, rightExpression);\n                        case "/":\n                            return new Divide(leftExpression, rightExpression);\n                        default:\n                            throw new Exception("Unknown operator");\n                    }\n                }\n                else\n                {\n                    throw new Exception("Unable to parse expression");\n                }\n            }\n        }\n\n        private string RemoveParenthesis(string expression)\n        {\n            if (expression.Contains("("))\n            {\n                expression = expression.Trim();\n\n                int level = 0;\n                int pos = 0;\n\n                foreach (char token in expression.ToCharArray())\n                {\n                    pos++;\n                    switch (token)\n                    {\n                        case \'(\':\n                            level++;\n                            break;\n                        case \')\':\n                            level--;\n                            break;\n                    }\n\n                    if (level == 0)\n                    {\n                        break;\n                    }\n                }\n\n                if (level == 0 &amp;&amp; pos == expression.Length)\n                {\n                    expression = expression.Substring(1, expression.Length - 2);\n                    expression = RemoveParenthesis(expression);\n                }\n            }\n            return expression;\n        }\n\n        private int ParseExpression(string expression)\n        {\n            int winningLevel = 0;\n            byte winningTokenWeight = 0;\n            int winningPos = 0;\n\n            int level = 0;\n            int pos = 0;\n\n            foreach (char token in expression.ToCharArray())\n            {\n                pos++;\n\n                switch (token)\n                {\n                    case \'(\':\n                        level++;\n                        break;\n                    case \')\':\n                        level--;\n                        break;\n                }\n\n                if (level &lt;= winningLevel)\n                {\n                    if (OperatorWeight(token) &gt; winningTokenWeight)\n                    {\n                        winningLevel = level;\n                        winningTokenWeight = OperatorWeight(token);\n                        winningPos = pos;\n                    }\n                }\n            }\n            return winningPos;\n        }\n\n        private byte OperatorWeight(char value)\n        {\n            switch (value)\n            {\n                case \'+\':\n                case \'-\':\n                    return 3;\n                case \'*\':\n                    return 2;\n                case \'/\':\n                    return 1;\n                default:\n                    return 0;\n            }\n        }\n    }\n\n    // -------------------------------------------------------\n\n    class ExpressionTree : ExpressionNodeBase\n    {\n        protected NodeBase _rootNode;\n\n        public ExpressionTree(string expression)\n        {\n            _rootNode = GetNode(expression);\n        }\n\n        public override double Value\n        {\n            get\n            {\n                return _rootNode.Value;\n            }\n        }\n    }\n\n    // -------------------------------------------------------\n\n    abstract class OperatorNodeBase : ExpressionNodeBase\n    {\n        protected NodeBase _leftNode;\n        protected NodeBase _rightNode;\n\n        public OperatorNodeBase(string leftExpression, string rightExpression)\n        {\n            _leftNode = GetNode(leftExpression);\n            _rightNode = GetNode(rightExpression);\n\n        }\n    }\n\n    // -------------------------------------------------------\n\n    class Add : OperatorNodeBase\n    {\n        public Add(string leftExpression, string rightExpression)\n            : base(leftExpression, rightExpression)\n        {\n        }\n\n        public override double Value\n        {\n            get\n            {\n                return _leftNode.Value + _rightNode.Value;\n            }\n        }\n    }\n\n    // -------------------------------------------------------\n\n    class Subtract : OperatorNodeBase\n    {\n        public Subtract(string leftExpression, string rightExpression)\n            : base(leftExpression, rightExpression)\n        {\n        }\n\n        public override double Value\n        {\n            get\n            {\n                return _leftNode.Value - _rightNode.Value;\n            }\n        }\n    }\n\n    // -------------------------------------------------------\n\n    class Divide : OperatorNodeBase\n    {\n        public Divide(string leftExpression, string rightExpression)\n            : base(leftExpression, rightExpression)\n        {\n        }\n\n        public override double Value\n        {\n            get\n            {\n                return _leftNode.Value / _rightNode.Value;\n            }\n        }\n    }\n\n    // -------------------------------------------------------\n\n    class Multiply : OperatorNodeBase\n    {\n        public Multiply(string leftExpression, string rightExpression)\n            : base(leftExpression, rightExpression)\n        {\n        }\n\n        public override double Value\n        {\n            get\n            {\n                return _leftNode.Value * _rightNode.Value;\n            }\n        }\n    }\n}\n</code></pre>\n'}, {'answer_id': 19599052, 'author': 'mmierzwa', 'author_id': 2921510, 'author_profile': 'https://Stackoverflow.com/users/2921510', 'pm_score': 0, 'selected': False, 'text': '<p>Ok, here is my naive implementation. Sorry, I did not feel to use objects for that one but it is easy to convert. I feel a bit like evil Willy (from Steve\'s story).</p>\n\n<pre><code>#!/usr/bin/env python\n\n#tree structure [left argument, operator, right argument, priority level]\ntree_root = [None, None, None, None]\n#count of parethesis nesting\nparenthesis_level = 0\n#current node with empty right argument\ncurrent_node = tree_root\n\n#indices in tree_root nodes Left, Operator, Right, PRiority\nL, O, R, PR = 0, 1, 2, 3\n\n#functions that realise operators\ndef sum(a, b):\n    return a + b\n\ndef diff(a, b):\n    return a - b\n\ndef mul(a, b):\n    return a * b\n\ndef div(a, b):\n    return a / b\n\n#tree evaluator\ndef process_node(n):\n    try:\n        len(n)\n    except TypeError:\n        return n\n    left = process_node(n[L])\n    right = process_node(n[R])\n    return n[O](left, right)\n\n#mapping operators to relevant functions\no2f = {\'+\': sum, \'-\': diff, \'*\': mul, \'/\': div, \'(\': None, \')\': None}\n\n#converts token to a node in tree\ndef convert_token(t):\n    global current_node, tree_root, parenthesis_level\n    if t == \'(\':\n        parenthesis_level += 2\n        return\n    if t == \')\':\n        parenthesis_level -= 2\n        return\n    try: #assumption that we have just an integer\n        l = int(t)\n    except (ValueError, TypeError):\n        pass #if not, no problem\n    else:\n        if tree_root[L] is None: #if it is first number, put it on the left of root node\n            tree_root[L] = l\n        else: #put on the right of current_node\n            current_node[R] = l\n        return\n\n    priority = (1 if t in \'+-\' else 2) + parenthesis_level\n\n    #if tree_root does not have operator put it there\n    if tree_root[O] is None and t in o2f:\n            tree_root[O] = o2f[t]\n            tree_root[PR] = priority\n            return\n\n    #if new node has less or equals priority, put it on the top of tree\n    if tree_root[PR] &gt;= priority:\n        temp = [tree_root, o2f[t], None, priority]\n        tree_root = current_node = temp\n        return\n\n    #starting from root search for a place with higher priority in hierarchy\n    current_node = tree_root\n    while type(current_node[R]) != type(1) and priority &gt; current_node[R][PR]:\n        current_node = current_node[R]\n    #insert new node\n    temp = [current_node[R], o2f[t], None, priority]\n    current_node[R] = temp\n    current_node = temp\n\n\n\ndef parse(e):\n    token = \'\'\n    for c in e:\n        if c &lt;= \'9\' and c &gt;=\'0\':\n            token += c\n            continue\n        if c == \' \':\n            if token != \'\':\n                convert_token(token)\n                token = \'\'\n            continue\n        if c in o2f:\n            if token != \'\':\n                convert_token(token)\n            convert_token(c)\n            token = \'\'\n            continue\n        print "Unrecognized character:", c\n    if token != \'\':\n        convert_token(token)\n\n\ndef main():\n    parse(\'(((3 * 4) / (1 + 2)) + 5)\')\n    print tree_root\n    print process_node(tree_root)\n\nif __name__ == \'__main__\':\n    main()\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/12516', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/25/']