Shunting-yard algorithm parser in Python

parser.py

# Algorithm description taken from here:
# https://en.wikipedia.org/wiki/Shunting-yard_algorithm#The_algorithm_in_detail

test = '3 * f(f(0*4),2,f(1,2+3),1)';

associativity = {'+': False, '-': False, '*': False} #False = left, True = right
precedence = {'+': 2, '-': 2, '*': 3}
i = 0
out = []
stack = []

def peek(l):
    if (len(l) == 0):
        return None
    else:
        return l[len(l) - 1]

# While there are tokens to be read:
while (i < len(test)):
    print (out, stack)
    # Read a token.
    tok = test[i]

    # If the token is a number, then add it to the output queue.
    if (tok.isdigit() or tok is 'a' or tok is 'b' or tok is 'c' or tok is 'd'):
        out.append(tok)
    # If the token is a function token, then push it onto the stack.
    elif (tok is 'f'):
        stack.append(tok)
    # If the token is a function argument separator (e.g., a comma):
    elif (tok is ','):
        # Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.
        while (peek(stack) != '('):
            out.append(stack.pop())
    # If the token is an operator, o1, then:
    elif (tok is '+' or tok is '*' or tok is '-'):
        # while there is an operator token, o2, at the top of the operator stack, and either
        hasOp = len(stack) > 0
        if (hasOp):
            op2 = peek(stack)
            hasOp = op2 == '+' or op2 == '*' or op2 == '-' # check if is an operator
        # o1 is left-associative and its precedence is less than or equal to that of o2,
        # or
        # o1 is right associative, and has precedence less than that of o2,
        if (hasOp):
            cond1 = not associativity[tok] and precedence[tok] <= precedence[op2]
            cond2 = associativity[tok] and precedence[tok] < precedence[op2]
            while (hasOp and (cond1 or cond2)):
                #then pop o2 off the operator stack, onto the output queue;
                out.append(stack.pop())
                hasOp = len(stack) > 0
                if (hasOp):
                    op2 = peek(stack)
                    hasOp = op2 == '+' or op2 == '*' or op2 == '-' #check if is an operator
                if (hasOp):
                    cond1 = not associativity[tok] and precedence[tok] <= precedence[op2]
                    cond2 = associativity[tok] and precedence[tok] < precedence[op2]
        # push o1 onto the operator stack.
        stack.append(tok)
    # If the token is a left parenthesis (i.e. "("), then push it onto the stack.
    elif (tok is '('):
        stack.append(tok)
    # If the token is a right parenthesis (i.e. ")"):
    elif (tok is ')'):
        # Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
        while (True):
            if (len(stack) > 0):
                tok = peek(stack)
                if (tok is '('):
                    # Pop the left parenthesis from the stack, but not onto the output queue.
                    stack.pop()
                    break
                else:
                    out.append(stack.pop())
            else:
                break
        # If the token at the top of the stack is a function token, pop it onto the output queue.
        if (len(stack) > 0):
            tok = peek(stack)
            if (tok is 'f'):
                out.append(stack.pop())

    i += 1

# When there are no more tokens to read:
# While there are still operator tokens in the stack:
# Pop the operator onto the output queue.
while (len(stack) > 0):
    out.append(stack.pop())

print out

parserwithfunc.py

# Algorithm description taken from here:
# https://en.wikipedia.org/wiki/Shunting-yard_algorithm#The_algorithm_in_detail

# test = '3*f(f(0*4),2,f(1,2+3),1)'; #4, 1, 2
# test = '3+2*4';
test = 'f(F(),5,6,F(3,f(1, 2),4),7)';

associativity = {'+': False, '-': False, '*': False} #False = left, True = right
precedence = {'+': 2, '-': 2, '*': 3}
i = 0
out = []
stack = []

class Token:
    def __init__(self, text):
        self.text = text
        self.argCount = 0
    def __str__(self):
        return self.text
    def __repr__(self):
        return self.text
    def isdigit(self):
        return self.text.isdigit()

def peek(l):
    if (len(l) == 0):
        return None
    else:
        return l[len(l) - 1]

# While there are tokens to be read:
while (i < len(test)):
    # Read a token.
    tok = Token(test[i])
    # Lookahead
    tok3 = None
    if (i + 2 < len(test)):
        tok3 = Token(test[i + 2])

    # If the token is a number, then add it to the output queue.
    if (tok.isdigit() or tok.text is 'a' or tok.text is 'b' or tok.text is 'c' or tok.text is 'd'):
        out.append(tok)
    # If the token is a function token, then push it onto the stack.
    elif (tok.text is 'f' or tok.text is 'F'):
        stack.append(tok)
        # Check if the function has no arguments
        if (tok3.text is ')'):
            tok.argCount = 0
        else:
            tok.argCount = 1
    # If the token is a function argument separator (e.g., a comma):
    elif (tok.text is ','):
        # Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.
        # for o in stack:
        k = len(stack) - 1
        while (k >= 0):
            o = stack[k]
            if (o.text is 'f' or o.text is 'F'):
                o.argCount += 1
                break
            k -= 1
        while (peek(stack).text != '('):
            out.append(stack.pop())
    # If the token is an operator, o1, then:
    elif (tok.text is '+' or tok.text is '*' or tok.text is '-'):
        # while there is an operator token, o2, at the top of the operator stack, and either
        hasOp = len(stack) > 0
        if (hasOp):
            op2 = peek(stack)
            hasOp = op2.text == '+' or op2.text == '*' or op2.text == '-' # check if is an operator
        # o1 is left-associative and its precedence is less than or equal to that of o2,
        # or
        # o1 is right associative, and has precedence less than that of o2,
        if (hasOp):
            cond1 = not associativity[tok.text] and precedence[tok.text] <= precedence[op2.text]
            cond2 = associativity[tok.text] and precedence[tok.text] < precedence[op2.text]
            while (hasOp and (cond1 or cond2)):
                #then pop o2 off the operator stack, onto the output queue;
                out.append(stack.pop())
                hasOp = len(stack) > 0
                if (hasOp):
                    op2 = peek(stack)
                    hasOp = op2.text == '+' or op2.text == '*' or op2.text == '-' #check if is an operator
                if (hasOp):
                    cond1 = not associativity[tok.text] and precedence[tok.text] <= precedence[op2.text]
                    cond2 = associativity[tok.text] and precedence[tok.text] < precedence[op2.text]
        # push o1 onto the operator stack.
        stack.append(tok)
    # If the token is a left parenthesis (i.e. "("), then push it onto the stack.
    elif (tok.text is '('):
        stack.append(tok)
    # If the token is a right parenthesis (i.e. ")"):
    elif (tok.text is ')'):
        # Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
        while (True):
            if (len(stack) > 0):
                tok = peek(stack)
                if (tok.text is '('):
                    # Pop the left parenthesis from the stack, but not onto the output queue.
                    stack.pop()
                    break
                else:
                    out.append(stack.pop())
            else:
                break
        # If the token at the top of the stack is a function token, pop it onto the output queue.
        if (len(stack) > 0):
            tok = peek(stack)
            if (tok.text is 'f' or tok.text is 'F'):
                out.append(stack.pop())

    print (out, stack)
    i += 1

# When there are no more tokens to read:
# While there are still operator tokens in the stack:
# Pop the operator onto the output queue.
while (len(stack) > 0):
    out.append(stack.pop())

# print (out, stack, fstack, fpointer)
print out
for o in out:
    if (o.text is 'f' or o.text is 'F'):
        print o.argCount