After solving AOJ in various ways, I touched on "Reverse Polish Notation" for the first time in a while. 0087:Strange Mathematical Expression So, after reviewing, I wrote Reverse Polish Notation (RPN) in Python.
When I learned it in a university class, I was only thinking, "Hey, I don't have to write parentheses one by one, and once I get used to it, it's easy to use." It seems to be compatible with computers just because you don't have to wait for all the numbers and operators you want to calculate without having to think hard.
Also, it seems to be compatible with Japanese people. For example 「(1 + 3) * (9 - 2)」 If you write the mathematical expression that you are familiar with (this is called infix notation) in reverse Polish notation 「1 3 + 9 2 - *」 It can be rewritten as. This means "Add 1 and 3, subtract 2 from 9 and multiply them." That's why the Japanese translation is done.
Writing is easy with Stack. -If the input is a numerical value, push to Stack -If the input is an operator, pop the numerical value for the argument from the Stack and calculate, and push the return value again. Just repeat this.
By the way, this is a digression, but do you know why it is called "(Reverse) Polish Notation"? I completely misunderstood that such a description method was common in Poland (eh?), But that is not the case. It is said that it is called because the logician Jan Ukasevich who originally devised this description method was Polish. If so, it might be called "Ukasevich notation", but his name Jan Łukasiewicz was roughly called "Polish notation" because it was difficult for the English people at that time to pronounce it. That's right.
It's ironic that Lisp, which has a reputation for having a lot of parentheses, uses Polish notation, which was devised to eliminate the parentheses that indicate priority.
[Wikipedia-Jan Łukasevich](https://ja.wikipedia.org/wiki/%E3%83%A4%E3%83%B3%E3%83%BB%E3%82%A6%E3%82%AB % E3% 82% B7% E3% 82% A7% E3% 83% B4% E3% 82% A3% E3% 83% 81)
rpn.py
def RPN(states):
'''
Function to calculate Reverse Polish Notation
'''
operator = {
'+': (lambda x, y: x + y),
'-': (lambda x, y: x - y),
'*': (lambda x, y: x * y),
'/': (lambda x, y: float(x) / y)
}
stack = []
print('RPN: %s' % states)
for index, z in enumerate(states):
if index > 0:
print(stack)
if z not in operator.keys():
stack.append(int(z))
continue
y = stack.pop()
x = stack.pop()
stack.append(operator[z](x,y))
print('%s %s %s =' % (x, z, y))
print(stack[0])
return stack[0]
def test():
print("OK" if RPN("37+621-*+") == 16 else "NG")
if __name__ == '__main__':
import sys
RPN(sys.argv[1])
test()
$ python rpn.py 37+621-*+
RPN: 37+621-*+
[3]
[3, 7]
3 + 7 =
[10]
[10, 6]
[10, 6, 2]
[10, 6, 2, 1]
2 - 1 =
[10, 6, 1]
6 * 1 =
[10, 6]
10 + 6 =
[16]
OK
When I was looking at some sites after reviewing, many people used the enumerate function for implementation, so I imitated it.
>>> a = ['a','b','c']
>>> for x in a:
... print(x)
...
a
b
c
For a list like
>>> a = ['a','b','c']
>>> for i,x in enumerate(a):
... print('%d : %d' % (i,x))
...
0 : a
1 : b
2 : c
You can do something like this.
Embarrassingly, I haven't used it until today, but I found it to be very useful when I want to retrieve the index and the element at the same time (in a case like this).
Last but not least, the calculator that can calculate PRN is [Amazon List](https://www.amazon.co.jp/RPN%E8%A8%98%E6%B3%95%E3%81% It was summarized in AE% E5% 87% BA% E6% 9D% A5% E3% 82% 8Bhp% E9% 9B% BB% E5% 8D% 93 / lm / R2KBMLT0XMHPJ2).
I want ... isn't it?
Recommended Posts