Make a calculator with 50 lines of Python code

Introduction

In this article, I will show you how to parse and calculate a four-arithmetic expression like a general-purpose calculator. When we're finished, we'll have a calculator that can handle expressions like 1+2*-(-3+2)/5.6+3. Of course, you can also expand it to be more powerful.

My original intention is to provide a simple and interesting course to explain grammatical analysis and formal grammar (compilation principle content). At the same time, I would like to introduce PlyPlus, a syntax parsing interface that I have been improving intermittently for several years. As an add-on to this course, we'll end up with a safe replacement for eval().

If you want to try the examples given in this article on your own computer, you should install PlyPlus first, using the command pip install plyplus . (Translator’s note: pip is a package management system, used to install software packages written in python. You can find the specific usage on Baidu or Google, so I won’t go into details.)

This article requires the inheritance of python Use to understand.

Grammar

For those of you who don’t understand how parsing and formal grammar work, here’s a quick overview: Formal grammar is a set of rules at different levels used to parse text. Each rule describes how the corresponding portion of the input text is composed.展 Here is an example to show how to analyze 1+2+3+4:

rule #1 -Add is Made of Add+Number

or Number

add: add'+'number

| number'+'number

;

The parser will look for add+number or number+number every time, and when it finds one, it will convert it to add. Basically, the goal of every parser is to find the highest level of expression abstraction possible.

Here are each step of the parser:

number + number + number + number

The first conversion turns all Numbers into "number" rules

[number + number] + number + number

Parse The processor found its first matching pattern!

[add + number] + number

After converting into a pattern, it starts looking for the next

[add + number]

add

These ordered symbols become two simple ones on one level Rules: number+number and add+number. This way, you only need to tell the computer if you solve these two problems, and it can parse the entire expression. In fact, no matter how long the addition sequence is, it can be solved! This is the power of formal grammar.

Operator precedence

Arithmetic expressions are not just a linear growth of symbols, operators create an implicit hierarchy, which is very suitable for representation in a formal grammar:

1 + 2 * 3 / 4 - 5 + 6

This is equivalent to:

1 + (2 * 3 / 4) - 5 + 6

We can represent the structure in this grammar through nested rules:

add: add+mul

| mul'+'mul

;

mul: mul '*; number

| number'*'number

;

By setting add to operate on mul instead of number, we get multiplication-first rule.

Let us simulate in our mind the process of using this magical parser to analyze 1+2*3*4:

number + number * number * number

number + [number * number] * number

parsing The parser doesn't know the result of number+number, so here's another option for it (the parser)

number + [mul * number]

number + mul

Now we're in a bit of a bind! The parser doesn't know what to do with it number+mul. We can distinguish this situation, but if we continue to explore, we will find that there are many different possibilities that were not considered, such as mul+number, add+number, add+add, etc.

So what should we do?

Fortunately, we can do a little "trick": we can think of a number itself as a product, and a product itself as a sum!

This idea may seem a little weird at first, but it does make sense:

add: add'+'mul

| mul'+'mul

| mul

;

mul: mul' *'number

| number'*'number

| number

;

But if mul can become add, and number can become mul, the contents of some lines will become redundant. Discarding them, we get:

add: add'+'mul

| mul

;

mul: mul'*'number

| number

;

Let's use this new one Let’s simulate running 1+2*3*4 using the grammar:

number + number * number * number

Now there is no rule corresponding to number*number, but the parser can "get creative"

number + [number] * number * number

number + [mul * number] * number

number + [mul * number]

[number] + mul

[mul] + mul

[add + mul]

add

successful! ! !

If you think this is amazing, then try to simulate it with another arithmetic expression, and then see how the expression can solve the problem step by step in the correct way. Or wait and read the next section to see how the computer works step by step!

Run the parser

Now that we have a pretty good idea of ​​how to make our grammar work, let’s write an actual grammar to apply:

start: add;

add: add add_symbol mul | mul;

mul: mul mul_symbol number | number;

number:'[d.]+'; // Regular expression of decimal number

mul_symbol:'*'|'/ ';// Match * or /

add_symbol:'+'|'-';// Match + or -

You might want to brush up on regular expressions, but regardless, the syntax is pretty straightforward. Let’s test it with an expression:

>>>fromplyplusimportGrammar

>>> g=Grammar("""...""")

>>>printg.parse('1+2* 3-5').pretty()

start

add

                                                                    add_symbol

                                                                                                                                mul_symbol

                                                                                                           ​ 5

Great job!

Take a closer look at the tree and see what level the parser chose.

If you wish to run this parser yourself and use your own expressions, all you need is Python. After installing Pip and PlyPlus, paste the above command into Python (remember to replace '...' with the actual syntax~).

Shape the tree

Plyplus will automatically create a tree, but it is not necessarily optimal. Putting number into mul and mul into add is great for creating a hierarchy, but now that we have a hierarchy they become a burden. We tell Plyplus to "expand" (i.e. delete) the rules by prefixing them.

An @ will often expand a rule, a # will flatten it, and a ? will expand it if it has a child node. In this case, ? is what we need.

start: add;

?add: add add_symbol mul | mul; '[d.]+';

mul_symbol:'*'|'/';

add_symbol:'+'|'-';

The tree looks like this under the new syntax:

>>> g= Grammar("""...""")

>>>printg.parse('1+2*3-5').pretty()

start

add

add

number

1

                add_symbol

                                                     

Number

3

add_symbol

- -

number

5

Oh, this is much simpler, Dare I say, it's very good.

Bracket processing and other features

So far, we are still obviously missing some necessary features: brackets, unit operators (-(1+2)), and allowing null characters in the middle of expressions. In fact, these features are very easy to implement. Let’s try them below.

An important concept needs to be introduced first: atoms. All operations that occur within an atom (in parentheses and unit operations) take precedence over all addition or multiplication operations (including bitwise operations). Since the atom is just a priority constructor and has no grammatical meaning, help us add the "@" symbol to ensure that it can be expanded during compilation.

The simplest way to allow spaces to appear in expressions is to use this explanation: add SPACE add_symbol SPACE mul | mul; But this explanation results in verbosity and poor readability. So, we need to make Plyplus always ignore spaces.

The following is the complete syntax, including the above features:

start: add;

?add: (add add_symbol)? mul;

?mul: (mul mul_symbol)? atom;

@atom: neg | number |'('add')';

neg:'-'atom;

number:'[d.]+';

mul_symbol:'*'|'/';

add_symbol:' +'|'-';

WHITESPACE:'[ t]+'(%ignore);

Please make sure you understand this syntax before proceeding to the next step: calculation!

Operation

Now, we can convert an expression into a hierarchical tree. We only need to scan the tree branch by branch to get the final result.

We are now going to start writing code. Before that, I need to explain two things about this tree:

1. Each branch is an instance containing the following two attributes:

Head: Rules Names (such as add or number); tail: contains a list of all sub -rules that match it.

2.Plyplus will delete unnecessary tags by default. In this example, '( ' , ')' and '-' are removed. But add and mul will have their own rules, and Plyplus will know that they are necessary and will not delete them. If you need to retain these tags, you can manually turn off this feature, but from my experience, it is better not to do this, but to manually modify the relevant syntax for better results.

Back to business, now we start writing code. We'll use a very simple converter to scan this tree. It starts scanning from the outermost branch until it reaches the root node, and our job is to tell it how to scan. If all goes well, it will always start scanning from the outermost layer! Let's see how it works.

>>>importoperator as op

>>>fromplyplusimportSTransformer

classCalc(STransformer):

def_bin_operator(self, exp):

arg1, operator_ symbol, arg2=exp.tail

F Operator_func = {'+': OP.ADD,

'-': OP.Sub,

'*': OP.mul,

'/': OP.DIV} [Operator_symbol]

O Returnoperator_func (ARG1, ARG2)

number = lambdaseld, exp: float (exp.tail [0])

neg = lambdaseld, exp: -exp.tail [0] __Default _ Lambdas ELF, EXP: exp.tail[0]

add=_bin_operator

mul=_bin_operator

Each method corresponds to a rule. If the method does not exist, the __default__ method will be called. We have omitted start, add_symbol and mul_symbol because they will only return their own branches.

I used float() to parse the numbers, which is a lazy method, but I could also use a parser to do it.

To make the statements neat, I used the operator module. For example add is basically 'lambda x,y: x+y' or something like that.

OK, now let’s run this code to check the results.

>>> Calc().transform( g.parse('1 + 2 * -(-3+2) / 5.6 + 30'))

31.357142857142858

What about eval()? 7

>>>eval('1 + 2 * -(-3+2) / 5.6 + 30')

31.357142857142858

Successful:)

Last step: REPL

For the sake of beauty, we Wrap it into a nice calculator REPL:

defmain():

calc=Calc()

whileTrue:

try:

s=raw_input('> ')

exceptEOFError :

break

IFS == '':

Break

Tree = Calc_grammar.parse (s)

PrintCalc.transform (Tree)

The complete code can be obtained from here:

https: //github.com/erezsh// plyplus/blob/master/examples/calc.py