How to Evaluate a Math Expression Given in String Form

How to evaluate a math expression given in string form?

With JDK1.6, you can use the built-in Javascript engine.

import javax.script.ScriptEngineManager;
import javax.script.ScriptEngine;
import javax.script.ScriptException;

public class Test {
  public static void main(String[] args) throws ScriptException {
    ScriptEngineManager mgr = new ScriptEngineManager();
    ScriptEngine engine = mgr.getEngineByName("JavaScript");
    String foo = "40+2";
    System.out.println(engine.eval(foo));
    } 
}

Evaluating a mathematical expression in a string form

You can modify the Shunting-yard algorithm to parse and evaluate in a single pass. There is no need for the intermediate step of converting to postfix. Restricting the problem to just the four standard mathematical operators with no parentheses doesn't change the basic approach.

Here's the standard Shunting-yard algorithm, from the linked article. I've added line numbers for reference below:

 1: while there are tokens to be read:
 2: read a token.
 3: if the token is a number, then push it to the output queue.
 4: if the token is an operator, then:
 5:     while (there is an operator at the top of the operator stack with
 6:         greater precedence) or (the operator at the top of the operator stack has
 7:                        equal precedence and
 8:                        the operator is left associative) and
 9:                      (the operator at the top of the stack is not a left bracket):
10:             pop operators from the operator stack, onto the output queue.
11:     push the read operator onto the operator stack.
12: if the token is a left bracket (i.e. "("), then:
13:     push it onto the operator stack.
14: if the token is a right bracket (i.e. ")"), then:
15:     while the operator at the top of the operator stack is not a left bracket:
16:         pop operators from the operator stack onto the output queue.
17:     pop the left bracket from the stack.
        /* if the stack runs out without finding a left bracket, then there are
18:     mismatched parentheses. */
19: if there are no more tokens to read:
20:     while there are still operator tokens on the stack:
21:         /* if the operator token on the top of the stack is a bracket, then
22:         there are mismatched parentheses. */
23:         pop the operator onto the output queue.
24: exit.

The modifications involve replacing the output queue with an operand stack: a stack of integers. So, for example, on line 3 instead of pushing the number to the output queue, you push the number onto the operand stack. This will of course require you to convert the character to an integer.

Then, on line 10 where you pop operators from the operator stack and push to the output queue, you instead:

1. Pop an operator
2. Pop two operands from the operand stack
3. Perform the operation
4. Push the result back onto the operand stack

You replace lines 16 and 23 with the same kind of logic.

If at any time when you're evaluating, there are not enough operands on the operand stack, then you have mismatched operators: something like 2+3+- (unless you decide to support unary + and unary -), or 2*/3.

When you've reached line 24, the operator stack is empty and the operand stack should contain a single value: the final result. If is more than one item on the operand stack, then you have too many operands (shouldn't happen).

So replace line 24 with a pop from the operand stack, and you can return that as the result.

The Shunting-yard is actually a very simplified version of the "recursive lexical parser" that you mentioned. But rather than building stack frames through recursion, it manipulates the stacks directly.

Modifying your code to do this shouldn't be too difficult. Below is a modified version of your convertToPostfix function, called evaluateInfix, that does it all in a single pass. Note that I'm not a Python programmer, so I won't guarantee the code to work flawlessly, but it should give you the idea:

def evaluateInfix(self, infix: list) -> int:
    operatorStack = collections.deque()
    operandStack = collections.deque()
    result = []
    for item in infix:
        if item.isdigit():
            val = convertDigitToNumber(item)  // however that's done
            // push to operand stack
            operandStack.append(val)
        else:
            while len(operatorStack) > 0 and self.has_higher_precedence(operatorStack[-1], item):
                // pop two operands from stack, evaluate, and push result
                // call this "pop and eval"
                op2 = operandStack[-1]
                operandStack.pop()
                op1 = operandStack[-1]
                operandStack.pop()
                operator = operatorStack[-1]
                operatorStack.pop()
                val = evaluate(operator, op1, op2) // this function evaluates op1 <operator> op2

                // push result back onto operand stack
                operandStack.append(val)
            operatorStack.append(item)
    while len(operatorStack) > 0:
        // insert "pop and eval" code here
    // at this point there should be a single value on the operand stack
    return operandStack[-1]

The evaluate function takes an operator and two operands, does the operation, and returns the result. So given ('+', 3, 5), it would compute 3+5, and return 8.

The idea here is that whenever you evaluate, you're taking two operands and a single operator.

Test case: 3+5*2.

       operand    operator
char    stack      stack
--------------------------
  3     [3]       []
  +     [3]       [+]
  5     [3,5]     [+]
  *     [3,5]     [+,*]
  2     [3,5,2]   [+,*]
 <end>
 at this point, we're at the end of the string.
 Pop 2 and 5 from the operand stack, pop * from the operator stack,
 and evaluate
        [3,10]    [+]
 pop and eval again
        [13]      []
 operator stack is empty. Pop result from operand stack and return.

Evaluating a mathematical expression in a string

Pyparsing can be used to parse mathematical expressions. In particular, fourFn.py
shows how to parse basic arithmetic expressions. Below, I've rewrapped fourFn into a numeric parser class for easier reuse.

from __future__ import division
from pyparsing import (Literal, CaselessLiteral, Word, Combine, Group, Optional,
                       ZeroOrMore, Forward, nums, alphas, oneOf)
import math
import operator

__author__ = 'Paul McGuire'
__version__ = '$Revision: 0.0 $'
__date__ = '$Date: 2009-03-20 $'
__source__ = '''http://pyparsing.wikispaces.com/file/view/fourFn.py
http://pyparsing.wikispaces.com/message/view/home/15549426
'''
__note__ = '''
All I've done is rewrap Paul McGuire's fourFn.py as a class, so I can use it
more easily in other places.
'''


class NumericStringParser(object):
    '''
    Most of this code comes from the fourFn.py pyparsing example

    '''

    def pushFirst(self, strg, loc, toks):
        self.exprStack.append(toks[0])

    def pushUMinus(self, strg, loc, toks):
        if toks and toks[0] == '-':
            self.exprStack.append('unary -')

    def __init__(self):
        """
        expop   :: '^'
        multop  :: '*' | '/'
        addop   :: '+' | '-'
        integer :: ['+' | '-'] '0'..'9'+
        atom    :: PI | E | real | fn '(' expr ')' | '(' expr ')'
        factor  :: atom [ expop factor ]*
        term    :: factor [ multop factor ]*
        expr    :: term [ addop term ]*
        """
        point = Literal(".")
        e = CaselessLiteral("E")
        fnumber = Combine(Word("+-" + nums, nums) +
                          Optional(point + Optional(Word(nums))) +
                          Optional(e + Word("+-" + nums, nums)))
        ident = Word(alphas, alphas + nums + "_$")
        plus = Literal("+")
        minus = Literal("-")
        mult = Literal("*")
        div = Literal("/")
        lpar = Literal("(").suppress()
        rpar = Literal(")").suppress()
        addop = plus | minus
        multop = mult | div
        expop = Literal("^")
        pi = CaselessLiteral("PI")
        expr = Forward()
        atom = ((Optional(oneOf("- +")) +
                 (ident + lpar + expr + rpar | pi | e | fnumber).setParseAction(self.pushFirst))
                | Optional(oneOf("- +")) + Group(lpar + expr + rpar)
                ).setParseAction(self.pushUMinus)
        # by defining exponentiation as "atom [ ^ factor ]..." instead of
        # "atom [ ^ atom ]...", we get right-to-left exponents, instead of left-to-right
        # that is, 2^3^2 = 2^(3^2), not (2^3)^2.
        factor = Forward()
        factor << atom + \
            ZeroOrMore((expop + factor).setParseAction(self.pushFirst))
        term = factor + \
            ZeroOrMore((multop + factor).setParseAction(self.pushFirst))
        expr << term + \
            ZeroOrMore((addop + term).setParseAction(self.pushFirst))
        # addop_term = ( addop + term ).setParseAction( self.pushFirst )
        # general_term = term + ZeroOrMore( addop_term ) | OneOrMore( addop_term)
        # expr <<  general_term
        self.bnf = expr
        # map operator symbols to corresponding arithmetic operations
        epsilon = 1e-12
        self.opn = {"+": operator.add,
                    "-": operator.sub,
                    "*": operator.mul,
                    "/": operator.truediv,
                    "^": operator.pow}
        self.fn = {"sin": math.sin,
                   "cos": math.cos,
                   "tan": math.tan,
                   "exp": math.exp,
                   "abs": abs,
                   "trunc": lambda a: int(a),
                   "round": round,
                   "sgn": lambda a: abs(a) > epsilon and cmp(a, 0) or 0}

    def evaluateStack(self, s):
        op = s.pop()
        if op == 'unary -':
            return -self.evaluateStack(s)
        if op in "+-*/^":
            op2 = self.evaluateStack(s)
            op1 = self.evaluateStack(s)
            return self.opn[op](op1, op2)
        elif op == "PI":
            return math.pi  # 3.1415926535
        elif op == "E":
            return math.e  # 2.718281828
        elif op in self.fn:
            return self.fn[op](self.evaluateStack(s))
        elif op[0].isalpha():
            return 0
        else:
            return float(op)

    def eval(self, num_string, parseAll=True):
        self.exprStack = []
        results = self.bnf.parseString(num_string, parseAll)
        val = self.evaluateStack(self.exprStack[:])
        return val

You can use it like this

nsp = NumericStringParser()
result = nsp.eval('2^4')
print(result)
# 16.0

result = nsp.eval('exp(2^4)')
print(result)
# 8886110.520507872

Evaluating a string as a mathematical expression in JavaScript

I've eventually gone for this solution, which works for summing positive and negative integers (and with a little modification to the regex will work for decimals too):

function sum(string) {
  return (string.match(/^(-?\d+)(\+-?\d+)*$/)) ? string.split('+').stringSum() : NaN;
}   

Array.prototype.stringSum = function() {
    var sum = 0;
    for(var k=0, kl=this.length;k<kl;k++)
    {
        sum += +this[k];
    }
    return sum;
}

I'm not sure if it's faster than eval(), but as I have to carry out the operation lots of times I'm far more comfortable runing this script than creating loads of instances of the javascript compiler

How to convert an arithmetic expression of a string type to an integer in Kotlin?

You cannot evaluate arithmetic in string expressions natively in kotlin or java. Either use a library (like exp4j, Javaluator, and SEpl) or write your own (refer to this thread).

---

Related Topics