ivanzjjcsu
BAN USERthe problem can be easily solved when a sorted array but not a BST, actually a pre-order(Left-Root-Right) travel of a BST is a sorted array. similarly a anti pre-order(Right-Root-Left) travel of a BST is also a sorted array but by the opposite order.So, the answer is: suppose two node pointers p1 and p2, for p1 we do a pre-order travel on BST and for every node p1 point to, we do a anti pre-order travel on BST until p2->val + p1->val <= x, if equality is satisfied,the answer is YES, otherwise,we do one step on p1( move one pre-order step on BST ), and do p2 as we do in array.
- ivanzjjcsu November 14, 2014#test.py
def is_num( c ):
if '0'<=c and c<='9' :
return True
else:
return False
def Eval():
while True:
str = raw_input("Enter your algebraic expression: " )
ope = []
num = []
len1 = len( str )
tmp = 0
for i in range( len1 ):
if is_num( str[i] ) :
tmp = tmp * 10 + (int)(str[i])
else :
while len(ope) > 0 and ( ope[-1]=='*' or ope[-1]=='/' ):
if ope[-1] == '*' :
tmp = num[-1] * tmp
else :
tmp = (float)(num[-1]) / tmp
del ope[-1]
del num[-1]
num.append( tmp )
tmp = 0
ope.append( str[i] )
while len(ope) > 0 and ( ope[-1]=='*' or ope[-1]=='/' ):
if ope[-1] == '*' :
tmp = num[-1] * tmp
else :
tmp = (float)(num[-1]) / tmp
del ope[-1]
del num[-1]
while len(ope) > 0 and ( ope[-1]=='+' or ope[-1]=='-' ):
if ope[-1] == '+' :
tmp = num[-1] + tmp
else :
tmp = num[-1] - tmp
del ope[-1]
del num[-1]
print "Value is: ",tmp
if __name__ == '__main__':
Eval()
- ivanzjjcsu July 30, 2015