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
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 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:
- Pop an operator
- Pop two operands from the operand stack
- Perform the operation
- 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 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
Evaluating arithmetic expressions from string in C++
I think you're looking for a simple recursive descent parser.
Here's a very simple example:
const char * expressionToParse = "3*2+4*1+(4+9)*6";
char peek()
{
return *expressionToParse;
}
char get()
{
return *expressionToParse++;
}
int expression();
int number()
{
int result = get() - '0';
while (peek() >= '0' && peek() <= '9')
{
result = 10*result + get() - '0';
}
return result;
}
int factor()
{
if (peek() >= '0' && peek() <= '9')
return number();
else if (peek() == '(')
{
get(); // '('
int result = expression();
get(); // ')'
return result;
}
else if (peek() == '-')
{
get();
return -factor();
}
return 0; // error
}
int term()
{
int result = factor();
while (peek() == '*' || peek() == '/')
if (get() == '*')
result *= factor();
else
result /= factor();
return result;
}
int expression()
{
int result = term();
while (peek() == '+' || peek() == '-')
if (get() == '+')
result += term();
else
result -= term();
return result;
}
int _tmain(int argc, _TCHAR* argv[])
{
int result = expression();
return 0;
}
How to evaluate a mathematical expression string the user passed to the program in python?
You probably want the sympify function.
You can also use the split() function to split the string the user types into an array, in order to get the other necessary arguments you mention needing.
For example:
from sympy import sympify
def evaluate(x, args[]):
# do stuff
return answer
in = input("Enter your expression: ")
x = in.split(",")
print(evaluate(x[0], [x[1], x[2], ...]))
EDIT: Just realized I forgot to describe how to use sympify, which is probably the most important thing with this question. Here is a simple example that should get across how to use it:
x = sympify("x**2")
How to evaluate a mathematical expression using strings and arrays in C
Look into the shunting yard algorithm and convert the string into reverse polish notation.
It will help if you also separate out number detection from symbol detection by reading the string one character at a time instead of just jumping to the operators.
After that, it is rather easy to perform the computation, as the inputs are ordered in a manner that makes a stack based calculator easy to implement.
Yes, you could do a full fledged recursive descent parser; but, for the relatively simple matter of algebraic expressions, they are overkill.
--- Edited because I see that there's controversy over tools vs techniques ---
I see a lot of people mentioning lexx and yacc. They are great tools, they are also overkill for what you need. It's like saying to open a carpentry shop when you want to replace a board on your fence. You don't need to learn another language to handle your math language, and lexx and yacc will require you to learn their domain specific configuration language to build the parser for your domain specific language. That's a lot of languages for a simple, solved problem.
Lexx and Yacc are great if you want to build a mathematical tree of your data; however, RPN is a mathematical tree of your data stored in a list of two fundamental node types (data) and (operation).
(a)(b)(c) // three "data nodes"
(a)(b)(+) // two "data nodes" and one operation node.
This allows one to use a stack based machine (very easy to implement). The machine has an "instruction set" of
if (x is data) { push X onto the top of the stack }
if (x is operation) {
pop the operation's required parameters.
pass them to the operation.
push the result on the stack
}
so assuming you had a '+' operator, the expression 3 + 5 + 6 would convert to RPN 3 5 + 6 + and the stack would look like (during processing)
<empty>
(3)
(3)(5)
(8)
(8)(6)
(14)
The primary reason to convert to RPN is not because it's necessary, it's because it makes the rest of your program much easier to implement. Imagine 3 + 5 * 7 converted to RPN, you have 3 5 7 * + which means that you don't have to do anything special with evaluation "machine" language. Note that (3 + 5) * 7 converts to RPN 3 5 + 7 *. In short, you reduce the complexity of the evaluation engine by massaging your input data to be less ambiguous.
Lexx and Yacc provide a lot of "configurability" to allow you to accomplish the same thing; however, you are not going to be configuring lexx and yacc to do anything special here, so the configurable interface doesn't buy you much. It's like having a multiple selection knob when you only need an on-off switch.
Now, if you want to build any kind of parser, where you are not aware of any kind of future rules which might be added; then definately choose lexx and yacc. But a simple algebraic expression parser is far too "solved" a problem to bring in the big guns. Use a shunting algorthim and break your problem down into
simple scanner to identify the main types of "tokens", NUMBER, +, -, /, *, (, and )
shunting algorithim to convert the "list" of tokens into a RPN list
a stack to hold the "memory" of the evaluation "machine"
the "machine" pull / push / evaluate loop
This has the added benefits of being able to develop the pieces independently, so you can verify each step without the entire framework being in place. Lexx and Yacc promote adding your code to their framework, so unless you take steps to do otherwise, you might have to debug the entire thing as one big piece.
Related Topics
Decode HTML Entities in Python String
Why Does Multiprocessing Use Only a Single Core After I Import Numpy
What Do I Use on Linux to Make a Python Program Executable
Understanding Python Subprocess.Check_Output'S First Argument and Shell=True
Convert Xml/Html Entities into Unicode String in Python
Using Pip3: Module "Importlib._Bootstrap" Has No Attribute "Sourcefileloader"
Standard_Init_Linux.Go:178: Exec User Process Caused "Exec Format Error"
Run Interactive Bash With Popen and a Dedicated Tty Python
How to Unescape HTML Entities in a String in Python 3.1
How to Make a Python Script Run Like a Service or Daemon in Linux
Cross-Platform Space Remaining on Volume Using Python
Is There a Python Equivalent to Java'S Awt Robot Class
Checking If Element Exists With Python Selenium
Shebang Notation: Python Scripts on Windows and Linux
Set Chrome Browser Binary Through Chromedriver in Python
System-Wide Mutex in Python on Linux