# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(S):
inputList = S.split()
inputList = inputList[::-1]
currentInput = ""
resultList = []
while inputList:
currentInput = inputList.pop()
if currentInput == "POP":
if resultList: #if not empty
resultList.pop()
#print(resultList)
else:
return -1
elif currentInput == "DUP":
if resultList:
resultList.append(resultList[-1])
#print(resultList)
elif currentInput == "+":
if len(resultList) < 2:
return -1
sum = resultList[-1] + resultList[-2]
if sum > (2**20) - 1:
return -1
else:
resultList.pop()
resultList.pop()
resultList.append(sum)
#print(resultList)
elif currentInput == "-":
if len(resultList) < 2:
return -1
diff = resultList[-1] - resultList[-2]
if diff < 0:
return -1
else:
resultList.pop()
resultList.pop()
resultList.append(diff)
#print(resultList)
elif currentInput.isdigit():
n = int(currentInput)
if not(0 <= n and n <= (2**20 -1)):
return -1
resultList.append(n)
#print(resultList)
if not resultList:
return -1
else:
#print(resultList)
return resultList[-1]
print(solution("3 -"))
print (solution('13 DUP 4 POP 5 DUP + DUP + -'))
print (solution('4 5 6 - 7 +'))
IyB5b3UgY2FuIHdyaXRlIHRvIHN0ZG91dCBmb3IgZGVidWdnaW5nIHB1cnBvc2VzLCBlLmcuCiMgcHJpbnQgInRoaXMgaXMgYSBkZWJ1ZyBtZXNzYWdlIgoKZGVmIHNvbHV0aW9uKFMpOgogICAgaW5wdXRMaXN0ID0gUy5zcGxpdCgpCiAgICBpbnB1dExpc3QgPSBpbnB1dExpc3RbOjotMV0KICAgIGN1cnJlbnRJbnB1dCA9ICIiCiAgICByZXN1bHRMaXN0ID0gW10KICAgIHdoaWxlIGlucHV0TGlzdDoKICAgICAgICBjdXJyZW50SW5wdXQgPSBpbnB1dExpc3QucG9wKCkKICAgICAgICBpZiBjdXJyZW50SW5wdXQgPT0gIlBPUCI6CiAgICAgICAgICAgIGlmIHJlc3VsdExpc3Q6ICAjaWYgbm90IGVtcHR5CiAgICAgICAgICAgICAgICByZXN1bHRMaXN0LnBvcCgpCiAgICAgICAgICAgICAgICAjcHJpbnQocmVzdWx0TGlzdCkKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIHJldHVybiAtMQogICAgICAgIGVsaWYgY3VycmVudElucHV0ID09ICJEVVAiOgogICAgICAgICAgICBpZiByZXN1bHRMaXN0OgogICAgICAgICAgICAgICAgcmVzdWx0TGlzdC5hcHBlbmQocmVzdWx0TGlzdFstMV0pCiAgICAgICAgICAgICAgICAjcHJpbnQocmVzdWx0TGlzdCkKCiAgICAgICAgZWxpZiBjdXJyZW50SW5wdXQgPT0gIisiOgogICAgICAgICAgICBpZiBsZW4ocmVzdWx0TGlzdCkgPCAyOgogICAgICAgICAgICAgICAgcmV0dXJuIC0xCgogICAgICAgICAgICAgICAgCiAgICAgICAgICAgIHN1bSA9IHJlc3VsdExpc3RbLTFdICsgcmVzdWx0TGlzdFstMl0gCiAgICAgICAgICAgIGlmIHN1bSA+ICgyKioyMCkgLSAxOgogICAgICAgICAgICAgICAgcmV0dXJuIC0xCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICByZXN1bHRMaXN0LnBvcCgpCiAgICAgICAgICAgICAgICByZXN1bHRMaXN0LnBvcCgpCiAgICAgICAgICAgICAgICByZXN1bHRMaXN0LmFwcGVuZChzdW0pCiAgICAgICAgICAgICAgICAjcHJpbnQocmVzdWx0TGlzdCkKCiAgICAgICAgZWxpZiBjdXJyZW50SW5wdXQgPT0gIi0iOgogICAgICAgICAgICBpZiBsZW4ocmVzdWx0TGlzdCkgPCAyOgogICAgICAgICAgICAgICAgcmV0dXJuIC0xCiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgZGlmZiA9IHJlc3VsdExpc3RbLTFdIC0gcmVzdWx0TGlzdFstMl0KICAgICAgICAgICAgaWYgZGlmZiA8IDA6CiAgICAgICAgICAgICAgICByZXR1cm4gLTEKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIHJlc3VsdExpc3QucG9wKCkKICAgICAgICAgICAgICAgIHJlc3VsdExpc3QucG9wKCkKICAgICAgICAgICAgICAgIHJlc3VsdExpc3QuYXBwZW5kKGRpZmYpCiAgICAgICAgICAgICAgICAjcHJpbnQocmVzdWx0TGlzdCkKCiAgICAgICAgZWxpZiBjdXJyZW50SW5wdXQuaXNkaWdpdCgpOgogICAgICAgICAgICBuID0gaW50KGN1cnJlbnRJbnB1dCkKICAgICAgICAgICAgaWYgbm90KDAgPD0gbiBhbmQgbiA8PSAoMioqMjAgLTEpKToKICAgICAgICAgICAgICAgIHJldHVybiAtMQogICAgICAgICAgICByZXN1bHRMaXN0LmFwcGVuZChuKQogICAgICAgICAgICAjcHJpbnQocmVzdWx0TGlzdCkKCiAgICAKICAgIGlmIG5vdCByZXN1bHRMaXN0OgogICAgICAgIHJldHVybiAtMQogICAgZWxzZToKICAgICAgICAjcHJpbnQocmVzdWx0TGlzdCkKICAgICAgICByZXR1cm4gcmVzdWx0TGlzdFstMV0KICAgICAgICAKcHJpbnQoc29sdXRpb24oIjMgLSIpKQpwcmludCAoc29sdXRpb24oJzEzIERVUCA0IFBPUCA1IERVUCArIERVUCArIC0nKSkKcHJpbnQgKHNvbHV0aW9uKCc0IDUgNiAtIDcgKycpKQ==