Python parser that makes parentheses according arithmetic priority

Question

How to make a parser that will make parentheses according arithmetical priority in expressions using the pyparsing library? for example * has higher priority than +.

It should do like this:

»> print(wholeexp.parseString('3+5-2')) 
[[['3', '+', '5'], '-', '2']] 
»> print(wholeexp.parseString('3+(5-2)')) 
[['3', '+', ['5', '-', '2']]] 
»> print(wholeexp.parseString('3+5-2*4')) 
[[['3', '+', '5'], '-', ['2', '*', '4']]]

I tried the following, but it doesn't work very well. How should we change expr here:

from pyparsing import *

numb = Word(nums)
leftpar = Suppress('(')
rightpar = Suppress(')')

expr = Forward()
expr << Or( [numb,
    Group(leftpar + expr + "+" + expr + rightpar),
    Group(leftpar + expr + "-" + expr + rightpar),
    Group(leftpar + expr + "*" + expr + rightpar)] )

wholeexp = expr + StringEnd()

Have you checked [this documentation](https://pyparsing.wikispaces.com/file/view/SimpleCalc.py)? — Sangbok Lee, Mar 31 '17 at 17:12
A recursive descent parser will help: https://en.wikipedia.org/wiki/Recursive_descent_parser. Or a Shunting-yard algorithm: https://en.wikipedia.org/wiki/Shunting-yard_algorithm. But first see this SO question to decide which to choose: http://stackoverflow.com/questions/28256/equation-expression-parser-with-precedence . — rajah9, Mar 31 '17 at 17:19

score 1 · Answer 1 · answered Apr 02 '17 at 21:21

Your approach is similar to that used in this pyparsing example: http://pyparsing.wikispaces.com/file/view/fourFn.py . But more recent versions of pyparsing introduced operatorPrecedence, more recently renamed infixNotation, and your 4-function arithmetic expression parser looks like this:

import pyparsing as pp

integer = pp.pyparsing_common.integer()

four_fn_arith_expr = pp.infixNotation(integer,
                                    [
                                        # leading sign
                                        (pp.oneOf("+ -"), 1, pp.opAssoc.RIGHT,),
                                        # multiplication and division
                                        (pp.oneOf("* /"), 2, pp.opAssoc.LEFT,),
                                        # addition and subtraction
                                        (pp.oneOf("+ -"), 2, pp.opAssoc.LEFT,),
                                    ])

Here are your test cases run with this parser:

tests = """
    3+5-2
    3+(5-2)
    3+5--2
    3+5-2*4
    """
four_fn_arith_expr.runTests(tests, fullDump=False)

Gives:

3+5-2
[[3, '+', 5, '-', 2]]

3+(5-2)
[[3, '+', [5, '-', 2]]]

3+5--2
[[3, '+', 5, '-', ['-', 2]]]

3+5-2*4
[[3, '+', 5, '-', [2, '*', 4]]]

we need parser that will go from left to right and after arithmetic op. will make parentheses according to priority, f.e. »> print(wholeexp.parseString('3+5-2')) [[['3', '+', '5'], '-', '2']] »> print(wholeexp.parseString('3+(5-2)')) [['3', '+', ['5', '-', '2']]] »> print(wholeexp.parseString('3+5-2*4')) [[['3', '+', '5'], '-', ['2', '*', '4']]] print(expr.parseString('3+5-4-2')) [[[['3', '+', '5'], '-', '4'], '-', '2']] using Forward and specific functions. help me please, thank you! — parYosef, Apr 05 '17 at 21:55
This remaining transformation is left as an exercise for the OP. — PaulMcG, Apr 06 '17 at 03:11
Pyparsing is no longer hosted on wikispaces.com. Go to https://github.com/pyparsing/pyparsing — PaulMcG, Aug 27 '18 at 13:03

Bigbadboybob · Answer 2 · 2017-03-31T17:38:50.233

This article seems promising: Simple Top-Down Parsing in Python I know it's a lot but scroll to the bottom of the "Streamlining Token Class Generation" section and you will see it in action. I personally couldn't get it to work because of an error: AttributeError: 'generator' object has no attribute 'next' but I'm pretty sure it has to do with the fact that the next method was changed in python 3.0. The code's to complicated for me to understand and fix the problem but you might have better luck.

Edit: Just ran it in python 2.7 and it worked. You can either run it in an older version of python or go through the code and try to fix it.

Python parser that makes parentheses according arithmetic priority

2 Answers2