# Parsing mathematical expressions

This topic is 5460 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi. I am just wondering how I might parse mathematical expression in a scripting language. My method is to have a compiler to translate my language into "virtual opcodes" For example, consider this expression: variable=2*2+4; That expression would translate to the following virtual opcodes. PUSH 2 // Pushes 2 onto the stack PUSH 2 // Pushes 2 onto the stack MULTIPLY // Multiplies next two items in stack and pushes result PUSH 4 // Pushes 4 onto stack ADD // adds next two items on stack SETVAR variable // sets variable to value on top of stack However, I am having a bit of difficulty. I am wondering how I might implement order of operations in parsing an expression. For example, how might I parse the following expression into virtual opcodes (following the order of operations where multiplication and division are done first) variable=4+2*5+8/2; Thank you for your time.

##### Share on other sites
If you don't want to bother yourself with operator precedence and what not, use Lisp-like syntax, it should be much easier to parse:

(+ 4 (* 2 5) (/ 8 2))

[Edited by - Diodor on October 10, 2004 2:41:17 AM]

##### Share on other sites
The easiest parsing algorithm to implement manually (without using automatic parser generators such as yacc/bison) is called recursive descent. The idea is rather simple; it is basically translating a grammar written in BNF (Backus-Naur Form) directly into programming language.

Here's an example in pseudo that parses arbitrary arithmetic operations consisting of additions, subtractions, multiplications, divisions and negations. Parentheses are supported.

// peek() returns the next token from stream// get() returns and consumes the next token// require() gets the next token and throws an error if it doesn't match the token given as parameter// add_op() pushes an opcode into the list of opcodes// parse addition and subtractionparse_arithmetic(){ // parse the left hand side parse_term(); while(peek() == '+' || peek() == '-') {  token op = get();  // parse the right hand side  parse_term();  add_op(op == '+' ? ADD : SUB); }}// parse multiplication and divisionparse_term(){ parse_factor(); while(peek() == '*' || peek() == '/') {  token op = get();  parse_term();  add_op(op == '*' ? MUL : DIV); }}// parse negation, parentheses, numbersparse_factor(){ if(peek() == '(') {  get();  parse_arithmetic();  require(')'); } else if(peek() == '-') {  get();  parse_factor();  add_op(NEG); } else if(peek() == number) {  add_op(PUSH, get().value); }}

HTH, Johannes

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 22
• 17
• 46