Using Python, How can I evaluate an expression in the form of prefix notation, concatenated?

Question

I am currently working on python tasks on a website called singpath. The question arises:

Evaluating a Prefix Create a function that evaluates an arithmetic expression as a prefix notation without spaces or syntax errors. The expression is specified as a string, all numbers in the expression are integers 0 ~ 9, and the operators - + (addition), - (subtraction), * (multiplication), / (division),% (modulo), which work the same way as in Python. Prefix notation, also known as Polish notation, is a form of notation for logic, arithmetic and algebra. it places the statements to the left of the operands. If the arity of the operators is fixed, the result is a syntax in which there are no brackets or other brackets that can still be parsed without ambiguity.

---

It seems simple enough, but the string condenses without spaces in the input to plan the data. How can I separate data from a row without importing modules? Also, how could I use the data results to solve this equation? Also keep in mind that Singpath solutions must be in ONE that cannot use methods that cannot be found in the python standard library. It also includes the functions declared in the solution: S

Examples:

>>> eval_prefix("+34") 7 >>> eval_prefix("*−567") -7 >>> eval_prefix("-*33+2+11") 5 >>> eval_prefix("-+5*+1243") 14 >>> eval_prefix("*+35-72") 40 >>> eval_prefix("%3/52") 1 

See my dot without spaces D:

Answer 1

OK, not as fun as the alex jordan lamba / reduce solution, but it doesn't choke on garbage input. This is a kind of recursive score parser meets the abomination of bubble flicker (I think it can be a little more efficient when it finds a solvable part than just jumping back to the beginning .;)

 import operator def eval_prefix(expr): d = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.div, # for 3.x change this to operator.truediv '%': operator.mod} for n in range(10): d[str(n)] = n e = list(d.get(e, None) for e in expr) i = 0 while i + 3 <= len(e): o, l, r = e[i:i+3] if type(o) == type(operator.add) and type(l) == type(r) == type(0): e[i:i+3] = [o(l, r)] i = 0 else: i += 1 if len(e) != 1: print 'Error in expression:', expr return 0 else: return e[0] def test(s, v): r = eval_prefix(s) print s, '==', v, r, r == v test("+34", 7) test("*-567", -7) test("-*33+2+11", 5) test("-+5*+1243", 14) test("*+35-72", 40) test("%3/52", 1) test("****", 0) test("-5bob", 10) 

Answer 2

I think the decisive bit here is "all numbers in the expression are integers 0 ~ 9". All numbers have a single digit. You do not need spaces to find out where one number ends and the next begins. You can access numbers directly by their string index, as lckknght said.

To convert characters in a string to integers for calculation, use ord (ch) - 48 (because "0" has an ASCII code of 48). So, to get the number stored in position 5 of the input, use ord (input [5]) - 48.

To evaluate nested expressions, you can call your function recursively. The essential assumption here is that for an operator there are always exactly two operators.

Answer 3

Limiting the "one function" is not as bad as you think. Python allows you to define functions inside functions. After all, defining a function is nothing more than assigning a function to a variable (usually new). In this case, I think you will want to use recursion. Although this can also be done without an extra function, it might be easier for you to define an additional recursion function for it. This is not a problem for your limits:

 def eval_prefix (data): def handle_operator (operator, rest): # You fill this in. # and this, too. 

That should be enough hint (if you want to use a recursive approach).

Answer 4

Well, does one liner fit? The reduction in python3 is hidden in functools A bit lispy :)

 eval_prefix = lambda inp:\ reduce(lambda stack, symbol:\ ( (stack+[symbol]) if symbol.isdigit() \ else \ ( stack[:-2]+\ [str( eval( stack[-1]+symbol+stack[-2] ) ) ] ) ), inp[::-1], [])[0] 

Answer 5

The hint you are most likely looking for is "repeatable strings":

 def eval_prefix(data): # setup state machine for symbol_ in data: # update state machine 

Answer 6

Separating line items is very simple. All elements have one character long, so you can directly iterate (or index) the string to get it. Or, if you want to be able to manipulate values, you can pass a string to the list constructor.

Here are some examples of how this might work:

 string = "*-567" # iterating over each character, one at a time: for character in string: print(character) # prints one character from the string per line # accessing a specific character by index: third_char = string[2] # note indexing is zero-based, so 3rd char is at index 2 # transform string to list list_of_characters = list(string) # will be ["*", "-", "5", "6", "7"] 

As for solving the equation, I think there are two approaches.

One of them is to make your function recursive so that each call evaluates one action or literal. This is a little complicated, since you should use only one function (it would be much easier if you could have a recursive helper function called with a different API than the main non-recursive function).

Another approach is to create a stack of values ​​and operations that you expect to evaluate, taking only one iteration over the input string. This is probably easier given the limit of one function.