<p>I've developed an equation parser using a simple stack algorithm that will handle binary (+, -, |, &amp;, *, /, etc) operators, unary (!) operators, and parenthesis.</p>
<p>Using this method, however, leaves me with everything having the same precedence - it's evaluated left to right regardless of operator, although precedence can be enforced using parenthesis.</p>
<p>So right now &quot;1+11*5&quot; returns 60, not 56 as one might expect.</p>
<p>While this is suitable for the current project, I want to have a general purpose routine I can use for later projects.</p>
<p><strong>Edited for clarity:</strong></p>
<p>What is a good algorithm for parsing equations with precedence?</p>
<p>I'm interested in something simple to implement and understand that I can code myself to avoid licensing issues with available code.</p>
<p><strong>Grammar:</strong></p>
<p>I don't understand the grammar question - I've written this by hand.  It's simple enough that I don't see the need for YACC or Bison.  I merely need to calculate strings with equations such as &quot;2+3 * (42/13)&quot;.</p>
<p><strong>Language:</strong></p>
<p>I'm doing this in C, but I'm interested in an algorithm, not a language specific solution.  C is low level enough that it'll be easy to convert to another language should the need arise.</p>
<p><strong>Code Example</strong></p>
<p>I posted the <a href="http://web.archive.org/web/20171012060859/http://www.ubasics.com/simple_c_equation_parser" rel="noreferrer">test code for the simple expression parser</a> I was talking about above.  The project requirements altered and so I never needed to optimize the code for performance or space as it wasn't incorporated into the project.  It's in the original verbose form, and should be readily understandable.  If I do anything further with it in terms of operator precedence, I'll probably choose <a href="https://stackoverflow.com/questions/28256/equation-expression-parser-with-precedence/783132#783132">the macro hack</a> because it matches the rest of the program in simplicity.  If I ever use this in a real project, though, I'll be going for a more compact/speedy parser.</p>
<p><strong>Related question</strong></p>
<blockquote>
<p><a href="https://stackoverflow.com/questions/114586/smart-design-of-a-math-parser">Smart design of a math parser?</a></p>
</blockquote>
<p>-Adam</p>

[{'answer_id': 28272, 'author': 'OysterD', 'author_id': 2638, 'author_profile': 'https://Stackoverflow.com/users/2638', 'pm_score': 4, 'selected': False, 'text': '<p>It would help if you could describe the grammar you are currently using to parse. Sounds like the problem might lie there!</p>\n\n<p>Edit:</p>\n\n<p>The fact that you don\'t understand the grammar question and that \'you\'ve written this by hand\' very likely explains why you\'re having problems with expressions of the form \'1+11*5\' (i.e., with operator precedence). Googling for \'grammar for arithmetic expressions\', for example, should yield some good pointers. Such a grammar need not be complicated:</p>\n\n<pre><code>&lt;Exp&gt; ::= &lt;Exp&gt; + &lt;Term&gt; |\n          &lt;Exp&gt; - &lt;Term&gt; |\n          &lt;Term&gt;\n\n&lt;Term&gt; ::= &lt;Term&gt; * &lt;Factor&gt; |\n           &lt;Term&gt; / &lt;Factor&gt; |\n           &lt;Factor&gt;\n\n&lt;Factor&gt; ::= x | y | ... |\n             ( &lt;Exp&gt; ) |\n             - &lt;Factor&gt; |\n             &lt;Number&gt;\n</code></pre>\n\n<p>would do the trick for example, and can be trivially augmented to take care of some more complicated expressions (including functions for example, or powers,...).</p>\n\n<p>I suggest you have a look at <a href="https://stackoverflow.com/questions/28124/calculating-user-defined-formulas-with-c">this</a> thread, for example.</p>\n\n<p>Almost all introductions to grammars/parsing treat arithmetic expressions as an example.</p>\n\n<p>Note that using a grammar does not at all imply using a specific tool (<em>a la</em> Yacc, Bison,...). Indeed, you most certainly are already using the following grammar:</p>\n\n<pre><code>&lt;Exp&gt;  :: &lt;Leaf&gt; | &lt;Exp&gt; &lt;Op&gt; &lt;Leaf&gt;\n\n&lt;Op&gt;   :: + | - | * | /\n\n&lt;Leaf&gt; :: &lt;Number&gt; | (&lt;Exp&gt;)\n</code></pre>\n\n<p>(or something of the kind) without knowing it!</p>\n'}, {'answer_id': 28282, 'author': 'James A. Rosen', 'author_id': 1190, 'author_profile': 'https://Stackoverflow.com/users/1190', 'pm_score': 2, 'selected': False, 'text': '<p>Is there a language you want to use?  <a href="http://antlr.org/" rel="nofollow noreferrer">ANTLR</a> will let you do this from a Java perspective.  Adrian Kuhn has an excellent <a href="http://www.iam.unibe.ch/~akuhn/blog/2008/05/executable-grammar-dsl/" rel="nofollow noreferrer">writeup</a> on how to write an executable grammar in Ruby; in fact, his example is almost exactly your arithmetic expression example.</p>\n'}, {'answer_id': 28286, 'author': 'chakrit', 'author_id': 3055, 'author_profile': 'https://Stackoverflow.com/users/3055', 'pm_score': 2, 'selected': False, 'text': '<p>It depends on how "general" you want it to be.</p>\n\n<p>If you want it to be really really general such as be able to parse mathematical functions as well like sin(4+5)*cos(7^3) you will probably need a <strong>parse tree.</strong></p>\n\n<p>In which, I do not think that a complete implementation is proper to be pasted here. I\'d suggest that you check out one of the infamous "<a href="http://en.wikipedia.org/wiki/Dragon_book" rel="nofollow noreferrer">Dragon book</a>".</p>\n\n<p><strong>But if you just want precedence support</strong>, then you could do that by first converting the expression to postfix form in which an algorithm that you can copy-and-paste should be available from <a href="http://www.google.co.th/search?btnG=Google+Search&amp;q=convert%20infix%20to%20postfix%20notation" rel="nofollow noreferrer">google</a> or I think you can code it up yourself with a binary tree.</p>\n\n<p>When you have it in postfix form, then it\'s piece of cake from then on since you already understand how the stack helps.</p>\n'}, {'answer_id': 29124, 'author': 'Jared Updike', 'author_id': 2543, 'author_profile': 'https://Stackoverflow.com/users/2543', 'pm_score': 7, 'selected': True, 'text': '<h3>The hard way</h3>\n\n<p>You want a <a href="http://en.wikipedia.org/wiki/Recursive_descent_parser" rel="noreferrer">recursive descent parser</a>.</p>\n\n<p>To get precedence you need to think recursively, for example, using your sample string, </p>\n\n<pre><code>1+11*5\n</code></pre>\n\n<p>to do this manually, you would have to read the <code>1</code>, then see the plus and start a whole new recursive parse "session" starting with <code>11</code>... and make sure to parse the <code>11 * 5</code> into its own factor, yielding a parse tree with <code>1 + (11 * 5)</code>.</p>\n\n<p>This all feels so painful even to attempt to explain, especially with the added powerlessness of C. See, after parsing the 11, if the * was actually a + instead, you would have to abandon the attempt at making a term and instead parse the <code>11</code> itself as a factor. My head is already exploding. It\'s possible with the recursive decent strategy, but there is a better way...</p>\n\n<h3>The easy (right) way</h3>\n\n<p>If you use a GPL tool like Bison, you probably don\'t need to worry about licensing issues since the C code generated by bison is not covered by the GPL (IANAL but I\'m pretty sure GPL tools don\'t force the GPL on generated code/binaries; for example Apple compiles code like say, Aperture with GCC and they sell it without having to GPL said code).</p>\n\n<p><a href="http://www.gnu.org/software/bison" rel="noreferrer">Download Bison</a> (or something equivalent, ANTLR, etc.).</p>\n\n<p>There is usually some sample code that you can just run bison on and get your desired C code that demonstrates this four function calculator:</p>\n\n<p><a href="http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html" rel="noreferrer">http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html</a></p>\n\n<p>Look at the generated code, and see that this is not as easy as it sounds. Also, the advantages of using a tool like Bison are 1) you learn something (especially if you read the Dragon book and learn about grammars), 2) you avoid <a href="http://en.wikipedia.org/wiki/Not_Invented_Here" rel="noreferrer">NIH</a> trying to reinvent the wheel. With a real parser-generator tool, you actually have a hope at scaling up later, showing other people you know that parsers are the domain of parsing tools.</p>\n\n<hr>\n\n<p><strong>Update:</strong></p>\n\n<p>People here have offered much sound advice. My only warning against skipping the parsing tools or just using the Shunting Yard algorithm or a hand rolled recursive decent parser is that little toy languages<sup><a href="http://docs.garagegames.com/tgea/official/content/documentation/Scripting%20Reference/Introduction/TorqueScript.html" rel="noreferrer">1</a></sup> may someday turn into big actual languages with functions (sin, cos, log) and variables, conditions and for loops.</p>\n\n<p>Flex/Bison may very well be overkill for a small, simple interpreter, but a one off parser+evaluator may cause trouble down the line when changes need to be made or features need to be added. Your situation will vary and you will need to use your judgement; just don\'t <a href="http://docs.garagegames.com/tgea/official/content/documentation/Scripting%20Reference/Introduction/TorqueScript.html" rel="noreferrer">punish other people for your sins</a> <sup>[2]</sup> and build a less than adequate tool.</p>\n\n<p><strong>My favorite tool for parsing</strong></p>\n\n<p>The best tool in the world for the job is the <a href="http://book.realworldhaskell.org/read/using-parsec.html" rel="noreferrer">Parsec</a> library (for recursive decent parsers) which comes with the programming language Haskell. It looks a lot like <a href="http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form" rel="noreferrer">BNF</a>, or like some specialized tool or domain specific language for parsing (sample code [3]), but it is in fact just a regular library in Haskell, meaning that it compiles in the same build step as the rest of your Haskell code, and you can write arbitrary Haskell code and call that within your parser, and you can mix and match other libraries <em>all in the same code</em>. (Embedding a parsing language like this in a language other than Haskell results in loads of syntactic cruft, by the way. I did this in C# and it works quite well but it is not so pretty and succinct.)</p>\n\n<p><strong>Notes:</strong></p>\n\n<p><a href="http://docs.garagegames.com/tgea/official/content/documentation/Scripting%20Reference/Introduction/TorqueScript.html" rel="noreferrer">1</a> Richard Stallman says, in <a href="http://web.cecs.pdx.edu/~trent/gnu/tcl-not" rel="noreferrer">Why you should not use Tcl</a></p>\n\n<blockquote>\n  <p>The principal lesson of Emacs is that\n  a language for extensions should not\n  be a mere "extension language".  It\n  should be a real programming language,\n  designed for writing and maintaining\n  substantial programs. Because people\n  will want to do that!</p>\n</blockquote>\n\n<p>[2] Yes, I am forever scarred from using that "language".</p>\n\n<p>Also note that when I submitted this entry, the preview was correct, but <strong>SO\'s less than adequate parser ate my close anchor tag on the first paragraph</strong>, proving that parsers are not something to be trifled with because if you use regexes and one off hacks <strong>you will probably get something subtle and small wrong</strong>.</p>\n\n<p>[3] Snippet of a Haskell parser using Parsec: a four function calculator extended with exponents, parentheses, whitespace for multiplication, and constants (like pi and e).</p>\n\n<pre class="lang-hs prettyprint-override"><code>aexpr   =   expr `chainl1` toOp\nexpr    =   optChainl1 term addop (toScalar 0)\nterm    =   factor `chainl1` mulop\nfactor  =   sexpr  `chainr1` powop\nsexpr   =   parens aexpr\n        &lt;|&gt; scalar\n        &lt;|&gt; ident\n\npowop   =   sym "^" &gt;&gt;= return . (B Pow)\n        &lt;|&gt; sym "^-" &gt;&gt;= return . (\\x y -&gt; B Pow x (B Sub (toScalar 0) y))\n\ntoOp    =   sym "-&gt;" &gt;&gt;= return . (B To)\n\nmulop   =   sym "*" &gt;&gt;= return . (B Mul)\n        &lt;|&gt; sym "/" &gt;&gt;= return . (B Div)\n        &lt;|&gt; sym "%" &gt;&gt;= return . (B Mod)\n        &lt;|&gt;             return . (B Mul)\n\naddop   =   sym "+" &gt;&gt;= return . (B Add) \n        &lt;|&gt; sym "-" &gt;&gt;= return . (B Sub)\n\nscalar = number &gt;&gt;= return . toScalar\n\nident  = literal &gt;&gt;= return . Lit\n\nparens p = do\n             lparen\n             result &lt;- p\n             rparen\n             return result\n</code></pre>\n'}, {'answer_id': 33083, 'author': 'ljs', 'author_id': 3394, 'author_profile': 'https://Stackoverflow.com/users/3394', 'pm_score': 3, 'selected': False, 'text': '<p>I would suggest cheating and using the <a href="http://en.wikipedia.org/wiki/Shunting_yard_algorithm" rel="noreferrer">Shunting Yard Algorithm</a>. It\'s an easy means of writing a simple calculator-type parser and takes precedence into account.</p>\n\n<p>If you want to properly tokenise things and have variables, etc. involved then I would go ahead and write a recursive descent parser as suggested by others here, however if you simply require a calculator-style parser then this algorithm should be sufficient :-)</p>\n'}, {'answer_id': 47717, 'author': 'Pramod', 'author_id': 1386292, 'author_profile': 'https://Stackoverflow.com/users/1386292', 'pm_score': 7, 'selected': False, 'text': '<p>The <a href="http://en.wikipedia.org/wiki/Shunting_yard_algorithm" rel="noreferrer">shunting yard algorithm</a> is the right tool for this. Wikipedia is really confusing about this, but basically the algorithm works like this:</p>\n\n<p>Say, you want to evaluate 1 + 2 * 3 + 4. Intuitively, you "know" you have to do the 2 * 3 first, but how do you get this result? The key is to realize that when you\'re scanning the string from left to right, you will evaluate an operator when the operator that <strong>follows</strong> it has a lower (or equal to) precedence. In the context of the example, here\'s what you want to do:</p>\n\n<ol>\n<li>Look at: 1 + 2, don\'t do anything.</li>\n<li>Now look at 1 + 2 * 3, still don\'t do anything.</li>\n<li>Now look at 1 + 2 * 3 + 4, now you know that 2 * 3 has to to be  evaluated because the next operator has lower precedence.</li>\n</ol>\n\n<p>How do you implement this?</p>\n\n<p>You want to have two stacks, one for numbers, and another for operators. You push numbers onto the stack all the time. You compare each new operator with the one at the top of the stack, if the one on top of the stack has higher priority, you pop it off the operator stack, pop the operands off the number stack, apply the operator and push the result onto the number stack. Now you repeat the comparison with the top of stack operator. </p>\n\n<p>Coming back to the example, it works like this:</p>\n\n<p>N = [ ]\nOps = [ ]</p>\n\n<ul>\n<li>Read 1. N = [1], Ops = [ ]</li>\n<li>Read +. N = [1], Ops = [+]</li>\n<li>Read 2. N = [1 2], Ops = [+]</li>\n<li>Read <code>*</code>. N = [1 2], Ops = [+ *]</li>\n<li>Read 3. N = [1 2 3], Ops = [+ *]</li>\n<li>Read +. N = [1 2 3], Ops = [+ *]\n\n<ul>\n<li>Pop 3, 2 and execute 2<code>*</code>3, and push result onto N. N = [1 6], Ops = [+]</li>\n<li><code>+</code> is left associative, so you want to pop 1, 6 off as well and execute the +. N = [7], Ops = [].</li>\n<li>Finally push the [+] onto the operator stack. N = [7], Ops = [+].</li>\n</ul></li>\n<li>Read 4. N = [7 4]. Ops = [+].</li>\n<li>You\'re run out off input, so you want to empty the stacks now. Upon which you will get the result 11.</li>\n</ul>\n\n<p>There, that\'s not so difficult, is it? And it makes no invocations to any grammars or parser generators.</p>\n'}, {'answer_id': 114961, 'author': 'bart', 'author_id': 19966, 'author_profile': 'https://Stackoverflow.com/users/19966', 'pm_score': 4, 'selected': False, 'text': '<p>Long time ago, I made up my own parsing algorithm, that I couldn\'t find in any books on parsing (like the Dragon Book). Looking at the pointers to the Shunting Yard algorithm, I do see the resemblance.</p>\n\n<p>About 2 years ago, I made a post about it, complete with Perl source code, on <a href="http://www.perlmonks.org/?node_id=554516" rel="noreferrer">http://www.perlmonks.org/?node_id=554516</a>. It\'s easy to port to other languages: the first implementation I did was in Z80 assembler.</p>\n\n<p>It\'s ideal for direct calculation with numbers, but you can use it to produce a parse tree if you must.</p>\n\n<p><strong>Update</strong> Because more people can read (or run) Javascript, I\'ve reimplemented my parser in Javascript, after the code has been reorganized. The whole parser is under 5k of Javascript code (about 100 lines for the parser, 15 lines for a wrapper function) including error reporting, and comments.</p>\n\n<p>You can find a live demo at <a href="http://users.telenet.be/bartl/expressionParser/expressionParser.html" rel="noreferrer">http://users.telenet.be/bartl/expressionParser/expressionParser.html</a>.</p>\n\n<pre class="lang-js prettyprint-override"><code>// operator table\nvar ops = {\n   \'+\'  : {op: \'+\', precedence: 10, assoc: \'L\', exec: function(l,r) { return l+r; } },\n   \'-\'  : {op: \'-\', precedence: 10, assoc: \'L\', exec: function(l,r) { return l-r; } },\n   \'*\'  : {op: \'*\', precedence: 20, assoc: \'L\', exec: function(l,r) { return l*r; } },\n   \'/\'  : {op: \'/\', precedence: 20, assoc: \'L\', exec: function(l,r) { return l/r; } },\n   \'**\' : {op: \'**\', precedence: 30, assoc: \'R\', exec: function(l,r) { return Math.pow(l,r); } }\n};\n\n// constants or variables\nvar vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };\n\n// input for parsing\n// var r = { string: \'123.45+33*8\', offset: 0 };\n// r is passed by reference: any change in r.offset is returned to the caller\n// functions return the parsed/calculated value\nfunction parseVal(r) {\n    var startOffset = r.offset;\n    var value;\n    var m;\n    // floating point number\n    // example of parsing ("lexing") without aid of regular expressions\n    value = 0;\n    while("0123456789".indexOf(r.string.substr(r.offset, 1)) &gt;= 0 &amp;&amp; r.offset &lt; r.string.length) r.offset++;\n    if(r.string.substr(r.offset, 1) == ".") {\n        r.offset++;\n        while("0123456789".indexOf(r.string.substr(r.offset, 1)) &gt;= 0 &amp;&amp; r.offset &lt; r.string.length) r.offset++;\n    }\n    if(r.offset &gt; startOffset) {  // did that work?\n        // OK, so I\'m lazy...\n        return parseFloat(r.string.substr(startOffset, r.offset-startOffset));\n    } else if(r.string.substr(r.offset, 1) == "+") {  // unary plus\n        r.offset++;\n        return parseVal(r);\n    } else if(r.string.substr(r.offset, 1) == "-") {  // unary minus\n        r.offset++;\n        return negate(parseVal(r));\n    } else if(r.string.substr(r.offset, 1) == "(") {  // expression in parens\n        r.offset++;   // eat "("\n        value = parseExpr(r);\n        if(r.string.substr(r.offset, 1) == ")") {\n            r.offset++;\n            return value;\n        }\n        r.error = "Parsing error: \')\' expected";\n        throw \'parseError\';\n    } else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) {  // variable/constant name        \n        // sorry for the regular expression, but I\'m too lazy to manually build a varname lexer\n        var name = m[0];  // matched string\n        r.offset += name.length;\n        if(name in vars) return vars[name];  // I know that thing!\n        r.error = "Semantic error: unknown variable \'" + name + "\'";\n        throw \'unknownVar\';        \n    } else {\n        if(r.string.length == r.offset) {\n            r.error = \'Parsing error at end of string: value expected\';\n            throw \'valueMissing\';\n        } else  {\n            r.error = "Parsing error: unrecognized value";\n            throw \'valueNotParsed\';\n        }\n    }\n}\n\nfunction negate (value) {\n    return -value;\n}\n\nfunction parseOp(r) {\n    if(r.string.substr(r.offset,2) == \'**\') {\n        r.offset += 2;\n        return ops[\'**\'];\n    }\n    if("+-*/".indexOf(r.string.substr(r.offset,1)) &gt;= 0)\n        return ops[r.string.substr(r.offset++, 1)];\n    return null;\n}\n\nfunction parseExpr(r) {\n    var stack = [{precedence: 0, assoc: \'L\'}];\n    var op;\n    var value = parseVal(r);  // first value on the left\n    for(;;){\n        op = parseOp(r) || {precedence: 0, assoc: \'L\'}; \n        while(op.precedence &lt; stack[stack.length-1].precedence ||\n              (op.precedence == stack[stack.length-1].precedence &amp;&amp; op.assoc == \'L\')) {  \n            // precedence op is too low, calculate with what we\'ve got on the left, first\n            var tos = stack.pop();\n            if(!tos.exec) return value;  // end  reached\n            // do the calculation ("reduce"), producing a new value\n            value = tos.exec(tos.value, value);\n        }\n        // store on stack and continue parsing ("shift")\n        stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});\n        value = parseVal(r);  // value on the right\n    }\n}\n\nfunction parse (string) {   // wrapper\n    var r = {string: string, offset: 0};\n    try {\n        var value = parseExpr(r);\n        if(r.offset &lt; r.string.length){\n          r.error = \'Syntax error: junk found at offset \' + r.offset;\n            throw \'trailingJunk\';\n        }\n        return value;\n    } catch(e) {\n        alert(r.error + \' (\' + e + \'):\\n\' + r.string.substr(0, r.offset) + \'&lt;*&gt;\' + r.string.substr(r.offset));\n        return;\n    }    \n}\n</code></pre>\n'}, {'answer_id': 166821, 'author': 'axelclk', 'author_id': 24819, 'author_profile': 'https://Stackoverflow.com/users/24819', 'pm_score': 2, 'selected': False, 'text': '<p>I\'ve implemented a <a href="http://en.wikipedia.org/wiki/Recursive_descent_parser" rel="nofollow noreferrer">recursive descent parser</a> in Java in the <a href="http://matheclipse.org/en/MathEclipse_Parser" rel="nofollow noreferrer">MathEclipse Parser</a> project. It could also be used in as a <a href="http://code.google.com/webtoolkit/" rel="nofollow noreferrer">Google Web Toolkit</a> module</p>\n'}, {'answer_id': 186081, 'author': 'Eli Bendersky', 'author_id': 8206, 'author_profile': 'https://Stackoverflow.com/users/8206', 'pm_score': 4, 'selected': False, 'text': '<p>There\'s a nice article <a href="http://crockford.com/javascript/tdop/tdop.html" rel="nofollow noreferrer">here</a> about combining a simple recursive-descent parser with operator-precedence parsing. If you\'ve been recently writing parsers, it should be very interesting and instructive to read.</p>\n'}, {'answer_id': 186091, 'author': 'Goran', 'author_id': 23164, 'author_profile': 'https://Stackoverflow.com/users/23164', 'pm_score': 2, 'selected': False, 'text': '<p>I\'m currently working on a series of articles building a regular expression parser as a learning tool for design patterns and readable programing. You can take a look at <a href="http://www.readablecode.blogspot.com/" rel="nofollow noreferrer">readablecode</a>. The article presents a clear use of shunting yards algorithm.</p>\n'}, {'answer_id': 266975, 'author': 'Erik Forbes', 'author_id': 16942, 'author_profile': 'https://Stackoverflow.com/users/16942', 'pm_score': 2, 'selected': False, 'text': '<p>I wrote an expression parser in F# and <a href="http://shadowcoding.blogspot.com/2008/10/f-mindblow-simple-math-expression.html" rel="nofollow noreferrer">blogged about it here</a>. It uses the shunting yard algorithm, but instead of converting from infix to RPN, I added a second stack to accumulate the results of calculations. It correctly handles operator precedence, but doesn\'t support unary operators. I wrote this to learn F#, not to learn expression parsing, though.</p>\n'}, {'answer_id': 354146, 'author': 'Adam Davis', 'author_id': 2915, 'author_profile': 'https://Stackoverflow.com/users/2915', 'pm_score': 2, 'selected': False, 'text': '<p>I found this on the PIClist about the <a href="http://en.wikipedia.org/wiki/Shunting_yard_algorithm" rel="nofollow noreferrer">Shunting Yard algorithm</a>:</p>\n\n<blockquote>\n  <p>Harold  writes:</p>\n  \n  <blockquote>\n    <p>I remember reading, a long time ago, of an algorithm that converted\n    algebraic expressions to RPN for easy evaluation. Each infix value or\n    operator or parenthesis was represented by a railroad car on a\n    track. One\n    type of car split off to another track and the other continued straight\n    ahead. I don\'t recall the details (obviously!), but always thought it\n    would be interesting to code. This is back when I was writing 6800 (not\n    68000) assembly code.</p>\n  </blockquote>\n  \n  <p>This is the "shunting yard algorythm"\n  and it is what most machine parsers\n  use. See the article on parsing in\n  Wikipedia. An easy way to code the\n  shunting yard algorythm is to use two\n  stacks. One is the "push" stack and\n  the other the "reduce" or "result"\n  stack. Example:</p>\n  \n  <p>pstack = () // empty rstack = ()\n  input: 1+2*3 precedence = 10 // lowest\n  reduce = 0 // don\'t reduce</p>\n  \n  <p>start: token \'1\':  isnumber, put in\n  pstack (push) token \'+\':  isoperator \n  set precedence=2  if precedence &lt;\n  previous_operator_precedence then\n  reduce() // see below  put \'+\' in\n  pstack (push) token \'2\':  isnumber,\n  put in pstack (push) token \'*\': \n  isoperator, set precedence=1, put in\n  pstack (push) // check precedence as \n  // above token \'3\':  isnumber, put in\n  pstack (push) end of input, need to\n  reduce (goal is empty pstack) reduce()\n  //done</p>\n  \n  <p>to reduce, pop elements from the push\n  stack and put them into the result\n  stack, always swap the top 2 items on\n  pstack if they are of the form\n  \'operator\' \'number\':</p>\n  \n  <p>pstack: \'1\' \'+\' \'2\' \'<em>\' \'3\' rstack: ()\n  ... pstack: () rstack: \'3\' \'2\' \'</em>\' \'1\'\n  \'+\'</p>\n  \n  <p>if the expression would have been:</p>\n  \n  <p>1*2+3</p>\n  \n  <p>then the reduce trigger would have\n  been the reading of the token \'+\'\n  which has lower precendece than the\n  \'*\' already pushed, so it would have\n  done:</p>\n  \n  <p>pstack: \'1\' \'<em>\' \'2\' rstack: () ...\n  pstack: () rstack: \'1\' \'2\' \'</em>\'</p>\n  \n  <p>and then pushed \'+\' and then \'3\' and\n  then finally reduced:</p>\n  \n  <p>pstack: \'+\' \'3\' rstack: \'1\' \'2\' \'<em>\'\n  ... pstack: () rstack: \'1\' \'2\' \'</em>\' \'3\'\n  \'+\'</p>\n  \n  <p>So the short version is: push numbers,\n  when pushing operators check the\n  precedence of the previous operator.\n  If it was higher than the operator\'s\n  that is to be pushed now, first\n  reduce, then push the current\n  operator. To handle parens simply save\n  the precedence of the \'previous\'\n  operator, and put a mark on the pstack\n  that tells the reduce algorythm to\n  stop reducing when solving the inside\n  of a paren pair. The closing paren\n  triggers a reduction as does the end\n  of input, and also removes the open\n  paren mark from the pstack, and\n  restores the \'previous operation\'\n  precedence so parsing can continue\n  after the close paren where it left\n  off. This can be done with recursion\n  or without (hint: use a stack to store\n  the previous precedence when\n  encountering a \'(\' ...). The\n  generalized version of this is to use\n  a parser generator implemented\n  shunting yard algorythm, f.ex. using\n  yacc or bison or taccle (tcl analog of\n  yacc).</p>\n  \n  <p>Peter</p>\n</blockquote>\n\n<p>-Adam</p>\n'}, {'answer_id': 375748, 'author': 'Lawrence Dol', 'author_id': 8946, 'author_profile': 'https://Stackoverflow.com/users/8946', 'pm_score': 2, 'selected': False, 'text': '<p>I have posted source for an ultra compact (1 class, &lt; 10 KiB) <a href="http://tech.dolhub.com/Code/MathEval" rel="nofollow noreferrer">Java Math Evaluator</a> on my web site.  This is a recursive descent parser of the type that caused the cranial explosion for the poster of the accepted answer.</p>\n\n<p>It supports full precedence, parenthesis, named variables and single-argument functions.</p>\n'}, {'answer_id': 783132, 'author': 'Adam Davis', 'author_id': 2915, 'author_profile': 'https://Stackoverflow.com/users/2915', 'pm_score': 3, 'selected': False, 'text': '<p>Another resource for precedence parsing is the <a href="http://en.wikipedia.org/wiki/Operator-precedence_parser" rel="nofollow noreferrer">Operator-precedence parser</a> entry on Wikipedia.  Covers Dijkstra\'s shunting yard algorithm, and a tree alternate algorithm, but more notably covers a really simple macro replacement algorithm that can be trivially implemented in front of any precedence ignorant parser:</p>\n\n<pre class="lang-c prettyprint-override"><code>#include &lt;stdio.h&gt;\nint main(int argc, char *argv[]){\n  printf("((((");\n  for(int i=1;i!=argc;i++){\n    if(argv[i] &amp;&amp; !argv[i][1]){\n      switch(argv[i]){\n      case \'^\': printf(")^("); continue;\n      case \'*\': printf("))*(("); continue;\n      case \'/\': printf("))/(("); continue;\n      case \'+\': printf(")))+((("); continue;\n      case \'-\': printf(")))-((("); continue;\n      }\n    }\n    printf("%s", argv[i]);\n  }\n  printf("))))\\n");\n  return 0;\n}\n</code></pre>\n\n<p>Invoke it as:</p>\n\n<pre><code>$ cc -o parenthesise parenthesise.c\n$ ./parenthesise a \\* b + c ^ d / e\n((((a))*((b)))+(((c)^(d))/((e))))\n</code></pre>\n\n<p>Which is awesome in its simplicity, and very understandable.</p>\n'}, {'answer_id': 799702, 'author': 'Zifre', 'author_id': 83871, 'author_profile': 'https://Stackoverflow.com/users/83871', 'pm_score': 3, 'selected': False, 'text': '<p>Have you thought about using <a href="http://spirit.sourceforge.net/" rel="nofollow noreferrer">Boost Spirit</a>? It allows you to write EBNF-like grammars in C++ like this:</p>\n\n<pre class="lang-cxx prettyprint-override"><code>group       = \'(\' &gt;&gt; expression &gt;&gt; \')\';\nfactor      = integer | group;\nterm        = factor &gt;&gt; *((\'*\' &gt;&gt; factor) | (\'/\' &gt;&gt; factor));\nexpression  = term &gt;&gt; *((\'+\' &gt;&gt; term) | (\'-\' &gt;&gt; term));\n</code></pre>\n'}, {'answer_id': 1377838, 'author': 'PaulMcG', 'author_id': 165216, 'author_profile': 'https://Stackoverflow.com/users/165216', 'pm_score': 2, 'selected': False, 'text': '<p>A Python solution using pyparsing can be found <a href="https://github.com/pyparsing/pyparsing/blob/master/examples/fourFn.py" rel="nofollow noreferrer" title="here">here</a>.  Parsing infix notation with various operators with precedence is fairly common, and so pyparsing also includes the <code>infixNotation</code> (formerly <code>operatorPrecedence</code>) expression builder.  With it you can easily define boolean expressions using "AND", "OR", "NOT", for example.  Or you can expand your four-function arithmetic to use other operators, such as ! for factorial, or \'%\' for modulus, or add P and C operators to compute permutations and combinations.  You could write an infix parser for matrix notation, that includes handling of \'-1\' or \'T\' operators (for inversion and transpose).  The operatorPrecedence example of a 4-function parser (with \'!\' thrown in for fun) is <a href="https://github.com/pyparsing/pyparsing/blob/master/examples/simpleArith.py" rel="nofollow noreferrer" title="here">here</a> and a more fully featured parser and evaluator is <a href="https://github.com/pyparsing/pyparsing/blob/master/examples/eval_arith.py" rel="nofollow noreferrer" title="here">here</a>.</p>\n'}, {'answer_id': 2517349, 'author': 'Alsin', 'author_id': 63312, 'author_profile': 'https://Stackoverflow.com/users/63312', 'pm_score': 5, 'selected': False, 'text': '<p><a href="http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm" rel="noreferrer">http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm</a></p>\n\n<p>Very good explanation of different approaches:</p>\n\n<ul>\n<li>Recursive-descent recognition</li>\n<li>The shunting yard algorithm</li>\n<li>The classic solution</li>\n<li>Precedence climbing</li>\n</ul>\n\n<p>Written in simple language and pseudo-code.</p>\n\n<p>I like \'precedence climbing\' one.</p>\n'}, {'answer_id': 6802025, 'author': 'fasseg', 'author_id': 234922, 'author_profile': 'https://Stackoverflow.com/users/234922', 'pm_score': 2, 'selected': False, 'text': '<p>i released an expression parser based on <a href="http://en.wikipedia.org/wiki/Shunting-yard_algorithm" rel="nofollow">Dijkstra\'s Shunting Yard</a> algorithm, under the terms of the <a href="http://www.apache.org/licenses/LICENSE-2.0.html" rel="nofollow">Apache License 2.0</a>:</p>\n\n<p><a href="http://projects.congrace.de/exp4j/index.html" rel="nofollow">http://projects.congrace.de/exp4j/index.html</a></p>\n'}, {'answer_id': 10957347, 'author': 'CisBestLanguageOfAllTimes', 'author_id': 1445582, 'author_profile': 'https://Stackoverflow.com/users/1445582', 'pm_score': 3, 'selected': False, 'text': '<p>As you put your question there is no need for recursion whatsoever. The answer is three things: Postfix notation plus Shunting Yard algorithm plus Postfix expression evaluation:</p>\n\n<p>1). Postfix notation = invented to eliminate the need for explicit precedence specification. Read more on the net but here is the gist of it: infix expression ( 1 + 2 ) * 3 while easy for humans to read and process not very efficient for computing via machine. What is? Simple rule that says "rewrite expression by caching in precedence,then always process it left-to-right". So infix ( 1 + 2 ) * 3 becomes a postfix 12+3*. POST because operator is placed always AFTER the operands.</p>\n\n<p>2). Evaluating postfix expression. Easy. Read numbers off postfix string. Push them on a stack until an operator is seen. Check operator type - unary? binary? tertiary? Pop as many operands off stack as needed to evaluate this operator. Evaluate. Push result back on stack! And u r almost done. Keep doing so until stack has only one entry = value u r looking for.</p>\n\n<p>Let\'s do ( 1 + 2 ) * 3 which is in postfix is "12+3*". Read first number = 1. Push it on stack. Read next. Number = 2. Push it on stack. Read next. Operator. Which one? +. What kind? Binary = needs two operands. Pop stack twice = argright is 2 and argleft is 1. 1 + 2 is 3. Push 3 back on stack. Read next from postfix string. Its a number. 3.Push. Read next. Operator. Which one? *. What kind? Binary = needs two numbers -> pop stack twice. First pop into argright, second time into argleft. Evaluate operation - 3 times 3 is 9.Push 9 on stack. Read next postfix char. It\'s null. End of input. Pop stack onec = that\'s your answer.</p>\n\n<p>3). Shunting Yard is used to transform human (easily) readable infix expression into postfix expression (also human easily readable after some practice). Easy to code manually. See comments above and net.</p>\n'}, {'answer_id': 22297417, 'author': 'Josh S', 'author_id': 1137626, 'author_profile': 'https://Stackoverflow.com/users/1137626', 'pm_score': 1, 'selected': False, 'text': '<p>I know this is a late answer, but I\'ve just written a tiny parser that allows all operators (prefix, postfix and infix-left, infix-right and nonassociative) to have arbitrary precedence.  </p>\n\n<p>I\'m going to expand this for a language with arbitrary DSL support, but I just wanted to point out that one doesn\'t need custom parsers for operator precedence, one can use a generalized parser that doesn\'t need tables at all, and just looks up the precedence of each operator as it appears. People have been mentioning custom Pratt parsers or shunting yard parsers that can accept illegal inputs - this one doesn\'t need to be customized and (unless there\'s a bug) won\'t accept bad input. It isn\'t complete in a sense, it was written to test the algorithm and its input is in a form that will need some preprocessing, but there are comments that make it clear.</p>\n\n<p>Note some common kinds of operators are missing for instance the sort of operator used for indexing ie table[index] or calling a function function(parameter-expression, ...)\nI\'m going to add those, but think of both as postfix operators where what comes between the delimeters \'[\' and \']\' or \'(\' and \')\' is parsed with a different instance of the expression parser.  Sorry to have left that out, but the postfix part is in - adding the rest will probably almost double the size of the code.</p>\n\n<p>Since the parser is just 100 lines of racket code, perhaps I should just paste it here, I hope this isn\'t longer than stackoverflow allows.</p>\n\n<p>A few details on arbitrary decisions:</p>\n\n<p>If a low precedence postfix operator is competing for the same infix blocks as a low precedence prefix operator the prefix operator wins.  This doesn\'t come up in most languages since most don\'t have low precedence postfix operators.\n- for instance: ((data a) (left 1 +) (pre 2 not)(data b)(post 3 !) (left 1 +) (data c))\nis a+not b!+c where not is a prefix operator and ! is postfix operator and both have lower\nprecedence than + so they want to group in incompatible ways either as\n    (a+not b!)+c\nor as\n     a+(not b!+c)\nin these cases the prefix operator always wins, so the second is the way it parses</p>\n\n<p>Nonassociative infix operators are really there so that you don\'t have to pretend that operators that return different types than they take make sense together, but without having different expression types for each it\'s a kludge.  As such, in this algorithm, non-associative operators refuse to associate not just with themselves but with any operator with the same precedence.  That\'s a common case as &lt; &lt;= == >= etc don\'t associate with each other in most languages.   </p>\n\n<p>The question of how different kinds of operators (left, prefix etc) break ties on precedence is one that shouldn\'t come up, because it doesn\'t really make sense to give operators of different types the same precedence.  This algorithm does something in those cases, but I\'m not even bothering to figure out exactly what because such a grammar is a bad idea in the first place. </p>\n\n<pre class="lang-rkt prettyprint-override"><code>#lang racket\n;cool the algorithm fits in 100 lines!\n(define MIN-PREC -10000)\n;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp)\n;for example "not a*-7+5 &lt; b*b or c &gt;= 4"\n;which groups as: not ((((a*(-7))+5) &lt; (b*b)) or (c &gt;= 4))"\n;is represented as \'((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 &lt;)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 &gt;=)(data 4)) \n;higher numbers are higher precedence\n;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c))\n\n(struct prec-parse ([data-stack #:mutable #:auto]\n                    [op-stack #:mutable #:auto])\n  #:auto-value \'())\n\n(define (pop-data stacks)\n  (let [(data (car (prec-parse-data-stack stacks)))]\n    (set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))\n    data))\n\n(define (pop-op stacks)\n  (let [(op (car (prec-parse-op-stack stacks)))]\n    (set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))\n    op))\n\n(define (push-data! stacks data)\n    (set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks))))\n\n(define (push-op! stacks op)\n    (set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks))))\n\n(define (process-prec min-prec stacks)\n  (let [(op-stack (prec-parse-op-stack stacks))]\n    (cond ((not (null? op-stack))\n           (let [(op (car op-stack))]\n             (cond ((&gt;= (cadr op) min-prec) \n                    (apply-op op stacks)\n                    (set-prec-parse-op-stack! stacks (cdr op-stack))\n                    (process-prec min-prec stacks))))))))\n\n(define (process-nonassoc min-prec stacks)\n  (let [(op-stack (prec-parse-op-stack stacks))]\n    (cond ((not (null? op-stack))\n           (let [(op (car op-stack))]\n             (cond ((&gt; (cadr op) min-prec) \n                    (apply-op op stacks)\n                    (set-prec-parse-op-stack! stacks (cdr op-stack))\n                    (process-nonassoc min-prec stacks))\n                   ((= (cadr op) min-prec) (error "multiply applied non-associative operator"))\n                   ))))))\n\n(define (apply-op op stacks)\n  (let [(op-type (car op))]\n    (cond ((eq? op-type \'post)\n           (push-data! stacks `(,op ,(pop-data stacks) )))\n          (else ;assume infix\n           (let [(tos (pop-data stacks))]\n             (push-data! stacks `(,op ,(pop-data stacks) ,tos))))))) \n\n(define (finish input min-prec stacks)\n  (process-prec min-prec stacks)\n  input\n  )\n\n(define (post input min-prec stacks)\n  (if (null? input) (finish input min-prec stacks)\n      (let* [(cur (car input))\n             (input-type (car cur))]\n        (cond ((eq? input-type \'post)\n               (cond ((&lt; (cadr cur) min-prec)\n                      (finish input min-prec stacks))\n                     (else \n                      (process-prec (cadr cur)stacks)\n                      (push-data! stacks (cons cur (list (pop-data stacks))))\n                      (post (cdr input) min-prec stacks))))\n              (else (let [(handle-infix (lambda (proc-fn inc)\n                                          (cond ((&lt; (cadr cur) min-prec)\n                                                 (finish input min-prec stacks))\n                                                (else \n                                                 (proc-fn (+ inc (cadr cur)) stacks)\n                                                 (push-op! stacks cur)\n                                                 (start (cdr input) min-prec stacks)))))]\n                      (cond ((eq? input-type \'left) (handle-infix process-prec 0))\n                            ((eq? input-type \'right) (handle-infix process-prec 1))\n                            ((eq? input-type \'nonassoc) (handle-infix process-nonassoc 0))\n                            (else error "post op, infix op or end of expression expected here"))))))))\n\n;alters the stacks and returns the input\n(define (start input min-prec stacks)\n  (if (null? input) (error "expression expected")\n      (let* [(cur (car input))\n             (input-type (car cur))]\n        (set! input (cdr input))\n        ;pre could clearly work with new stacks, but could it reuse the current one?\n        (cond ((eq? input-type \'pre)\n               (let [(new-stack (prec-parse))]\n                 (set! input (start input (cadr cur) new-stack))\n                 (push-data! stacks \n                             (cons cur (list (pop-data new-stack))))\n                 ;we might want to assert here that the cdr of the new stack is null\n                 (post input min-prec stacks)))\n              ((eq? input-type \'data)\n               (push-data! stacks cur)\n               (post input min-prec stacks))\n              ((eq? input-type \'grouped)\n               (let [(new-stack (prec-parse))]\n                 (start (cdr cur) MIN-PREC new-stack)\n                 (push-data! stacks (pop-data new-stack)))\n               ;we might want to assert here that the cdr of the new stack is null\n               (post input min-prec stacks))\n              (else (error "bad input"))))))\n\n(define (op-parse input)\n  (let [(stacks (prec-parse))]\n    (start input MIN-PREC stacks)\n    (pop-data stacks)))\n\n(define (main)\n  (op-parse (read)))\n\n(main)\n</code></pre>\n'}, {'answer_id': 46722767, 'author': 'user4617883', 'author_id': 4617883, 'author_profile': 'https://Stackoverflow.com/users/4617883', 'pm_score': 1, 'selected': False, 'text': "<p>Here is a simple case recursive solution written in Java.  Note it does not handle negative numbers but you can do add that if you want to:</p>\n\n<pre><code>public class ExpressionParser {\n\npublic double eval(String exp){\n    int bracketCounter = 0;\n    int operatorIndex = -1;\n\n    for(int i=0; i&lt;exp.length(); i++){\n        char c = exp.charAt(i);\n        if(c == '(') bracketCounter++;\n        else if(c == ')') bracketCounter--;\n        else if((c == '+' || c == '-') &amp;&amp; bracketCounter == 0){\n            operatorIndex = i;\n            break;\n        }\n        else if((c == '*' || c == '/') &amp;&amp; bracketCounter == 0 &amp;&amp; operatorIndex &lt; 0){\n            operatorIndex = i;\n        }\n    }\n    if(operatorIndex &lt; 0){\n        exp = exp.trim();\n        if(exp.charAt(0) == '(' &amp;&amp; exp.charAt(exp.length()-1) == ')')\n            return eval(exp.substring(1, exp.length()-1));\n        else\n            return Double.parseDouble(exp);\n    }\n    else{\n        switch(exp.charAt(operatorIndex)){\n            case '+':\n                return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));\n            case '-':\n                return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));\n            case '*':\n                return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));\n            case '/':\n                return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));\n        }\n    }\n    return 0;\n}\n</code></pre>\n\n<p>}</p>\n"}, {'answer_id': 48446000, 'author': 'Viktor Shepel', 'author_id': 8244545, 'author_profile': 'https://Stackoverflow.com/users/8244545', 'pm_score': 1, 'selected': False, 'text': '<p>Algorithm could be easily encoded in C as recursive descent parser.</p>\n\n<pre class="lang-c prettyprint-override"><code>#include &lt;stdio.h&gt;\n#include &lt;ctype.h&gt;\n\n/*\n *  expression -&gt; sum\n *  sum -&gt; product | product "+" sum\n *  product -&gt; term | term "*" product\n *  term -&gt; number | expression\n *  number -&gt; [0..9]+\n */\n\ntypedef struct {\n    int value;\n    const char* context;\n} expression_t;\n\nexpression_t expression(int value, const char* context) {\n    return (expression_t) { value, context };\n}\n\n/* begin: parsers */\n\nexpression_t eval_expression(const char* symbols);\n\nexpression_t eval_number(const char* symbols) {\n    // number -&gt; [0..9]+\n    double number = 0;        \n    while (isdigit(*symbols)) {\n        number = 10 * number + (*symbols - \'0\');\n        symbols++;\n    }\n    return expression(number, symbols);\n}\n\nexpression_t eval_term(const char* symbols) {\n    // term -&gt; number | expression\n    expression_t number = eval_number(symbols);\n    return number.context != symbols ? number : eval_expression(symbols);\n}\n\nexpression_t eval_product(const char* symbols) {\n    // product -&gt; term | term "*" product\n    expression_t term = eval_term(symbols);\n    if (*term.context != \'*\')\n        return term;\n\n    expression_t product = eval_product(term.context + 1);\n    return expression(term.value * product.value, product.context);\n}\n\nexpression_t eval_sum(const char* symbols) {\n    // sum -&gt; product | product "+" sum\n    expression_t product = eval_product(symbols);\n    if (*product.context != \'+\')\n        return product;\n\n    expression_t sum = eval_sum(product.context + 1);\n    return expression(product.value + sum.value, sum.context);\n}\n\nexpression_t eval_expression(const char* symbols) {\n    // expression -&gt; sum\n    return eval_sum(symbols);\n}\n\n/* end: parsers */\n\nint main() {\n    const char* expression = "1+11*5";\n    printf("eval(\\"%s\\") == %d\\n", expression, eval_expression(expression).value);\n\n    return 0;\n}\n</code></pre>\n\n<p><sub>next libs might be useful:</sub>\n<sub><a href="https://github.com/viktor-shepel/yupana" rel="nofollow noreferrer">yupana</a> - strictly arithmetic operations;</sub>\n<sub><a href="https://github.com/codeplea/tinyexpr" rel="nofollow noreferrer">tinyexpr</a> - arithmetic operations + C math functions + one provided by user;</sub>\n<sub><a href="https://github.com/orangeduck/mpc" rel="nofollow noreferrer">mpc</a> - parser combinators</sub></p>\n\n<h2>Explanation</h2>\n\n<p>Let\'s capture sequence of symbols that represent algebraic expression.\nFirst one is a number, that is a decimal digit repeated one or more times.\n<sub>We will refer such notation as production rule.</sub></p>\n\n<pre><code>number -&gt; [0..9]+\n</code></pre>\n\n<p>Addition operator with its operands is another rule.\nIt is either <code>number</code> or any symbols that represents <code>sum "*" sum</code> sequence.</p>\n\n<pre><code>sum -&gt; number | sum "+" sum\n</code></pre>\n\n<p>Try substitute <code>number</code> into <code>sum "+" sum</code> that will be <code>number "+" number</code> which in turn could be expanded into <code>[0..9]+ "+" [0..9]+</code> that finally could be reduced to <code>1+8</code> which is correct addition expression.</p>\n\n<p>Other substitutions will also produce correct expression: <code>sum "+" sum</code> -> <code>number "+" sum</code> -> <code>number "+" sum "+" sum</code> -> <code>number "+" sum "+" number</code> -> <code>number "+" number "+" number</code> -> <code>12+3+5</code></p>\n\n<p>Bit by bit we could resemble set of production rules <sub>aka grammar</sub> that express all possible algebraic expression.</p>\n\n<pre><code>expression -&gt; sum\nsum -&gt; difference | difference "+" sum\ndifference -&gt; product | difference "-" product\nproduct -&gt; fraction | fraction "*" product\nfraction -&gt; term | fraction "/" term\nterm -&gt; "(" expression ")" | number\nnumber -&gt; digit+                                                                    \n</code></pre>\n\n<p>To control operator precedence alter position of its production rule against others. Look at grammar above and note that production rule for <code>*</code> is placed below <code>+</code> this will force <code>product</code> evaluate before <code>sum</code>.\nImplementation just combines pattern recognition with evaluation and thus closely mirrors production rules.</p>\n\n<pre class="lang-c prettyprint-override"><code>expression_t eval_product(const char* symbols) {\n    // product -&gt; term | term "*" product\n    expression_t term = eval_term(symbols);\n    if (*term.context != \'*\')\n        return term;\n\n    expression_t product = eval_product(term.context + 1);\n    return expression(term.value * product.value, product.context);\n}\n</code></pre>\n\n<p>Here we eval <code>term</code> first and return it if there is no <code>*</code> character after it <sub>this is left choise in our production rule</sub> otherwise - evaluate symbols after and return <code>term.value * product.value</code> <sub>this is right choise in our production rule i.e. <code>term "*" product</code></sub></p>\n'}, {'answer_id': 64399150, 'author': 'Charles Owen', 'author_id': 4151175, 'author_profile': 'https://Stackoverflow.com/users/4151175', 'pm_score': 0, 'selected': False, 'text': "<p>Actually there's a way to do this without recursion, which allows you to go through the entire expression once, character by character.  This is O(n) for time and space.  It takes all of 5 milliseconds to run even for a medium-sized expression.</p>\n<p>First, you'd want to do a check to ensure that your parens are balanced.  I'm not doing it here for simplicity.  Also, I'm acting as if this were a calculator.  Calculators do not apply precedence unless you wrap an expression in parens.</p>\n<p>I'm using two stacks, one for the operands and another for the operators.  I increase the priority of the operation whenever I reach an opening '(' paren and decrease the priority whenever I reach a closing ')' paren.  I've even revised the code to add in numbers with decimals.  This is in c#.</p>\n<p>NOTE: This doesn't work for signed numbers like negative numbers.  Probably is just a simple revision.</p>\n<pre><code>  internal double Compute(string sequence)\n    {\n        int priority = 0;\n        int sequenceCount = sequence.Length;            \n        for (int i = 0; i &lt; sequenceCount; i++) {\n            char s = sequence[i];                \n            if (Char.IsDigit(s)) {\n                double value = ParseNextNumber(sequence, i);\n                numberStack.Push(value);\n                i = i + value.ToString().Length - 1;\n            } else if (s == '+' || s == '-' || s == '*' || s == '/')  {                \n               Operator op = ParseNextOperator(sequence, i, priority);\n                CollapseTop(op, numberStack, operatorStack);\n                operatorStack.Push(op);\n            } if (s == '(') { priority++; ; continue; }\n            else if (s == ')') { priority--; continue; }\n        }\n        if (priority != 0) { throw new ApplicationException(&quot;Parens not balanced&quot;); }\n        CollapseTop(new Operator(' ', 0), numberStack, operatorStack);\n        if (numberStack.Count == 1 &amp;&amp; operatorStack.Count == 0) {\n            return numberStack.Pop();\n        }\n        return 0;\n    }    \n</code></pre>\n<p>Then to test this out:</p>\n<pre><code>Calculator c = new Calculator();\ndouble value = c.Compute(&quot;89.8+((9*3)+8)+(9*2)+1&quot;);\nConsole.WriteLine(string.Format(&quot;The sum of the expression is: {0}&quot;, (float)value));\n//prints out The sum of the expression is: 143.8\n</code></pre>\n"}, {'answer_id': 68577842, 'author': 'Carson', 'author_id': 9935654, 'author_profile': 'https://Stackoverflow.com/users/9935654', 'pm_score': 0, 'selected': False, 'text': '<p><em>Pure javascript, no dependencies needed</em></p>\n<p>I very like <a href="https://stackoverflow.com/a/114961/9935654">bart\'s answer</a>.</p>\n<p>and I do some modifications to read it easier, and also add support some function(and easily extend)</p>\n<pre class="lang-js prettyprint-override"><code>function Parse(str) {\n  try {\n    return parseExpr(str.replaceAll(&quot; &quot;, &quot;&quot;)) // Implement? See full code.\n  } catch (e) {\n    alert(e.message)\n  }\n}\n\nParse(&quot;123.45+3*22*4&quot;)\n</code></pre>\n<p>It can support as below</p>\n<pre class="lang-js prettyprint-override"><code>const testArray = [\n  //  Basic Test\n  [&quot;(3+5)*4&quot;, &quot;&quot;],\n  [&quot;123.45+3*22*4&quot;, &quot;&quot;],\n  [&quot;8%2&quot;, &quot;&quot;],\n  [&quot;8%3&quot;, &quot;&quot;],\n  [&quot;7/3&quot;, &quot;&quot;],\n  [&quot;2*pi*e&quot;, 2 * Math.atan2(0, -1) * Math.exp(1)],\n  [&quot;2**3&quot;, &quot;&quot;],\n\n  //  unary Test\n  [&quot;3+(-5)&quot;, &quot;&quot;],\n  [&quot;3+(+5)&quot;, &quot;&quot;],\n\n  //  Function Test\n  [&quot;pow{2,3}*2&quot;, 16],\n  [&quot;4*sqrt{16}&quot;, 16],\n  [&quot;round{3.4}&quot;, 3],\n  [&quot;round{3.5}&quot;, 4],\n  [&quot;((1+e)*3/round{3.5})%2&quot;, ((1 + Math.exp(1)) * 3 / Math.round(3.5)) % 2],\n  [&quot;round{3.5}+pow{2,3}&quot;, Math.round(3.5)+Math.pow(2,3)],\n]\n</code></pre>\n<h2>Full code</h2>\n<p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">\r\n<div class="snippet-code">\r\n<pre class="snippet-code-js lang-js prettyprint-override"><code>//  Main\n(() =&gt; {\n  window.onload = () =&gt; {\n    const nativeConsoleLogFunc = window.console.error\n    window.console.error = (...data) =&gt; { // Override native function, just for test.\n      const range = document.createRange()\n      const frag = range.createContextualFragment(`&lt;div&gt;${data}&lt;/div&gt;`)\n      document.querySelector("body").append(frag)\n      nativeConsoleLogFunc(...data)\n    }\n\n    // Add Enter event\n    document.querySelector(`input`).onkeyup = (keyboardEvent) =&gt; {\n      if (keyboardEvent.key === "Enter") {\n        const result = Parse(document.getElementById(\'expr\').value)\n        if (result !== undefined) {\n          alert(result)\n        }\n      }\n    }\n\n    const testArray = [\n      //  Basic Test\n      ["(3+5)*4", ""],\n      ["123.45+3*22*4", ""],\n      ["8%2", ""],\n      ["8%3", ""],\n      ["7/3", ""],\n      ["2*pi*e", 2 * Math.atan2(0, -1) * Math.exp(1)],\n      ["2**3", ""],\n\n      //  unary\n      ["3+(-5)", ""],\n      ["3+(+5)", ""],\n\n      //  Function Test\n      ["pow{2,3}*2", 16],\n      ["4*sqrt{16}", 16],\n      ["round{3.4}", 3],\n      ["round{3.5}", 4],\n      ["((1+e)*3/round{3.5})%2", ((1 + Math.exp(1)) * 3 / Math.round(3.5)) % 2],\n      ["round{3.5}+pow{2,3}", Math.round(3.5) + Math.pow(2, 3)],\n\n      //  error test\n      ["21+", ValueMissingError],\n      ["21+*", ParseError],\n      ["(1+2", ParseError], // miss ")"\n      ["round(3.12)", MissingParaError], // should be round{3.12}\n      ["help", UnknownVarError],\n    ]\n\n    for (let [testString, expected] of testArray) {\n      if (expected === "") {\n        expected = eval(testString) // Why don\'t you use eval instead of writing the function yourself? Because the browser may disable eval due to policy considerations. [CSP](https://content-security-policy.com/)\n      }\n      const actual = Parse(testString, false)\n\n      if (actual !== expected) {\n        if (actual instanceof Error &amp;&amp; actual instanceof expected) {\n          continue\n        }\n        console.error(`${testString} = ${actual}, value &lt;code&gt;${expected}&lt;/code&gt; expected`)\n      }\n    }\n  }\n})()\n\n//  Script\nclass UnknownVarError extends Error {\n}\n\nclass ValueMissingError extends Error {\n}\n\nclass ParseError extends Error {\n}\n\nclass MissingParaError extends Error {\n}\n\n/**\n * @description Operator\n * @param {string} sign "+", "-", "*", "/", ...\n * @param {number} precedence\n * @param {"L"|"R"} assoc associativity  left or right\n * @param {function} exec\n * */\nfunction Op(sign, precedence, assoc, exec = undefined) {\n  this.sign = sign\n  this.precedence = precedence\n  this.assoc = assoc\n  this.exec = exec\n}\n\nconst OpArray = [\n  new Op("+", 10, "L", (l, r) =&gt; l + r),\n  new Op("-", 10, "L", (l, r) =&gt; l - r),\n  new Op("*", 20, "L", (l, r) =&gt; l * r),\n  new Op("/", 20, "L", (l, r) =&gt; l / r),\n  new Op("%", 20, "L", (l, r) =&gt; l % r),\n  new Op("**", 30, "R", (l, r) =&gt; Math.pow(l, r))\n]\n\nconst VarTable = {\n  e: Math.exp(1),\n  pi: Math.atan2(0, -1), // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/atan2\n  pow: (x, y) =&gt; Math.pow(x, y),\n  sqrt: (x) =&gt; Math.sqrt(x),\n  round: (x) =&gt; Math.round(x),\n}\n\n/**\n * @param {Op} op\n * @param {Number} value\n * */\nfunction Item(op, value = undefined) {\n  this.op = op\n  this.value = value\n}\n\nclass Stack extends Array {\n  constructor(...items) {\n    super(...items)\n    this.push(new Item(new Op("", 0, "L")))\n  }\n\n  GetLastItem() {\n    return this[this.length - 1] // fast then pop // https://stackoverflow.com/a/61839489/9935654\n  }\n}\n\nfunction Cursor(str, pos) {\n  this.str = str\n  this.pos = pos\n  this.MoveRight = (step = 1) =&gt; {\n    this.pos += step\n  }\n  this.PeekRightChar = (step = 1) =&gt; {\n    return this.str.substring(this.pos, this.pos + step)\n  }\n\n  /**\n   * @return {Op}\n   * */\n  this.MoveToNextOp = () =&gt; {\n    const opArray = OpArray.sort((a, b) =&gt; b.precedence - a.precedence)\n    for (const op of opArray) {\n      const sign = this.PeekRightChar(op.sign.length)\n      if (op.sign === sign) {\n        this.MoveRight(op.sign.length)\n        return op\n      }\n    }\n    return null\n  }\n}\n\n/**\n * @param {Cursor} cursor\n * */\nfunction parseVal(cursor) {\n  let startOffset = cursor.pos\n\n  const regex = /^(?&lt;OpOrVar&gt;[^\\d.])?(?&lt;Num&gt;[\\d.]*)/g\n  const m = regex.exec(cursor.str.substr(startOffset))\n  if (m) {\n    const {groups: {OpOrVar, Num}} = m\n    if (OpOrVar === undefined &amp;&amp; Num) {\n      cursor.pos = startOffset + Num.length\n\n      if (cursor.pos &gt; startOffset) {\n        return parseFloat(cursor.str.substring(startOffset, startOffset + cursor.pos - startOffset)) // do not use string.substr() // It will be removed in the future. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Deprecated_and_obsolete_features#string_methods\n      }\n    }\n\n    if ("+-(".indexOf(OpOrVar) !== -1) {\n      cursor.pos++\n      switch (OpOrVar) {\n        case "+": // unary plus, for example: (+5)\n          return parseVal(cursor)\n        case "-":\n          return -(parseVal(cursor))\n        case "(":\n          const value = parseExpr(cursor)\n          if (cursor.PeekRightChar() === ")") {\n            cursor.MoveRight()\n            return value\n          }\n          throw new ParseError("Parsing error: \')\' expected")\n      }\n    }\n  }\n\n\n  //  below is for Variable or Function\n  const match = cursor.str.substring(cursor.pos).match(/^[a-z_][a-z0-9_]*/i) // https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/match\n\n  if (match) {\n    //  Variable\n    const varName = match[0]\n    cursor.MoveRight(varName.length)\n    const bracket = cursor.PeekRightChar(1)\n    if (bracket !== "{") {\n      if (varName in VarTable) {\n        const val = VarTable[varName]\n        if (typeof val === "function") {\n          throw new MissingParaError(`${varName} is a function, it needs big curly brackets`)\n        }\n        return val\n      }\n    }\n\n    //  is function\n    const regex = /{(?&lt;Para&gt;[^{]*)}/gm\n    const m = regex.exec(cursor.str.substring(cursor.pos))\n    if (m &amp;&amp; m.groups.Para !== undefined) {\n      const paraString = m.groups.Para\n      const para = paraString.split(\',\')\n      cursor.MoveRight(paraString.length + 2) // 2 = { + }\n      return VarTable[varName](...para)\n    }\n    throw new UnknownVarError(`unknown variable ${varName}`)\n  }\n\n  //  Handle Error\n  if (cursor.str.length === cursor.pos) { // example: 1+2+\n    throw new ValueMissingError(`Parsing error at end of string: value expected.`)\n  } else { // example: 1+2+*\n    throw new ParseError("Parsing error: unrecognized value")\n  }\n}\n\n/**\n * @param {string|Cursor} expr\n * */\nfunction parseExpr(expr) {\n  const stack = new Stack()\n  const cursor = (expr instanceof Cursor) ? expr : new Cursor(expr, 0)\n  while (1) {\n    let rightValue = parseVal(cursor)\n    const op = cursor.MoveToNextOp() ?? new Op("", 0, "L")\n\n    while (\n      op.precedence &lt; stack.GetLastItem().op.precedence ||\n      (op.precedence === stack.GetLastItem().op.precedence &amp;&amp; op.assoc === \'L\')) {\n      const lastItem = stack.pop()\n      if (!lastItem.op.exec) { // end reached\n        return rightValue\n      }\n      rightValue = lastItem.op.exec(lastItem.value, rightValue)\n    }\n\n    stack.push(new Item(op, rightValue))\n  }\n}\n\nfunction Parse(str, alertError = true) {\n  try {\n    return parseExpr(str.replaceAll(" ", ""))\n  } catch (e) {\n    if (alertError) {\n      alert(e.message)\n      return undefined\n    }\n    return e\n  }\n}</code></pre>\r\n<pre class="snippet-code-html lang-html prettyprint-override"><code>&lt;input type="text" id="expr" name="expr" placeholder="123.45+3*22*4"&gt;\n&lt;button onclick="const x = Parse(document.getElementById(\'expr\').value); if(x != null) alert(x);"&gt;\n  Calculate!\n&lt;/button&gt;</code></pre>\r\n</div>\r\n</div>\r\n</p>\n'}]
['https://Stackoverflow.com/questions/28256', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/2915/']