This is a prefix operation problem. We can solve it by using a stack.
The algorithm is as follows:
- Establish a connection with the server and get the complete question from the server
- Split the string into a list of operands and operators
- Initialize an empty stack
- Iterate the list:
- If the item is an operator: push into the stack
- If the item is an operand:
while size of stack > 0 and top of stack not in {mul,add,sub}:- If the top of the stack is an operand: pop the stack 2 times, the first popped item is an operand and the second is an operator (the operator guarantee to be one of {
mul,add,sub,neg,inc}). Do the operation and push the result into the stack - else if the top of the stack is one of {
neg,inc}: pop the top of the stack, do the operation and push the result into the stack - else: push the item into the stack (this case is that the top of the stack is one of {
mul,add,sub})
- If the top of the stack is an operand: pop the stack 2 times, the first popped item is an operand and the second is an operator (the operator guarantee to be one of {
- return the top of stack
Below is the python solution to this challenge:
import socket
op = {"mul", "add", "sub", "neg", "inc"}
oop = {"mul", "add", "sub"}
def calc(ss):
ss = ss.split()
st = []
for s in ss:
cur = s
if cur in op:
st.append(s)
else:
cur = int(cur)
while len(st) > 0 and st[len(st) - 1] not in oop:
if st[len(st) - 1] not in op: # a num
sec = st.pop()
o = st.pop()
if o == "add":
cur = int(cur) + int(sec)
elif o == "mul":
cur = int(cur) * int(sec)
elif o == "sub":
cur = int(sec) - int(cur)
else: # neg or inc
o = st.pop()
if o == "neg":
cur = -cur
else:
cur += 1
st.append(cur)
return st.pop()
def netcat(hostname, port):
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((hostname, port))
start = False
cnt = 0
while 1:
data = ""
while 1:
try:
d = s.recv(4096)
if len(d) <= 0:
break;
if d[len(d) - 1] == "\n":
data += d
break
data += d
except:
break
if cnt > 99:
print(data)
if data.startswith("You"):
data = data[18:]
if start:
try:
s.sendall("{}\n".format(calc(data)))
except:
print(data)
exit()
else:
s.sendall("START\n")
start = True
print("send start")
print(cnt)
cnt += 1
print("Connection closed.")
s.close()
netcat("challs.nusgreyhats.org", 15521)The flag is: grey{prefix_operation_is_easy_to_evaluate_right_W2MQshAYVpGVJPcw}