Convert recursive functions to iterative ones

Kiwi · 2010-05-02 05:26:14

I have two recursive functions, one or more of which I would like to convert to iterative. I would much appreciate either tips on turning them into iterative or (better yet) pseudocode or code in another language. >.> I have tried searching google for a few hours and most of what I have found is not very helpful. A lot of it is only for tail call recursive functions, which these are not....

These are examples of what construct tree parses (a different function converts them to a stack beforehand)

!  ((57+4)+(3/(4$(3-(9/8)))))
!  ((((5+3)/4)$2)+(((5-3)$2)/4))
!  ((15-(2$(2$(12-(5*2)))))+(((((15-3)/6)$2)*4)/8))

In each case the + should be the root node of the tree.

My regular stack type is LISTTYPE, TREENODE is my tree type, and I also have available a TREELISTTYPE which is a stack of TREENODEs, as well as push and pops for both of them.

IF (ASSOCIATED(foo) is equivalent to "!= NULL" in C, for this purpose, at least.

RECURSIVE FUNCTION construct_tree2(expression) RESULT(the_tree)
    IMPLICIT NONE
    TYPE(LISTTYPE), INTENT(INOUT) :: expression
    TYPE(TREENODE), POINTER :: leftexp, rightexp, the_tree
    CHARACTER(50) :: symbol, op_symbol, closeparen
    ALLOCATE(the_tree)
    ALLOCATE(leftexp)
    ALLOCATE(rightexp)

    symbol = pop(expression)

    IF (symbol == "(") THEN
        leftexp = construct_tree2(expression)

        op_symbol = pop(expression)
        IF (.NOT. isOperator(op_symbol)) THEN
            WRITE(*,*) "Expected an operator"
            STOP
        ENDIF

        rightexp = construct_tree2(expression)

        closeparen = pop(expression)
        IF (closeparen /= ")") THEN
            WRITE(*,*) "Unmatched '('"
            STOP
        ENDIF
        the_tree%rl => rightexp
        the_tree%ll => leftexp
        the_tree%charvalue = op_symbol
    ELSEIF (isNum(symbol)) THEN
        NULLIFY(the_tree%ll)
        NULLIFY(the_tree%rl)
        the_tree%charvalue = symbol
    ELSE
        WRITE(*,*) "Expected '(' or a number while parsing expression"
        STOP
    ENDIF
END FUNCTION construct_tree2

RECURSIVE SUBROUTINE post_order_tree_evaluation2(tree)
    IMPLICIT NONE
    TYPE(TREENODE), POINTER, intent(INOUT) :: tree
    IF (.NOT. ASSOCIATED(tree)) STOP
    IF((isOperator(tree%charvalue)) .AND. (.NOT. ASSOCIATED(tree%rl)) &
        .AND. (.NOT. ASSOCIATED(tree%ll))) STOP
    IF(ASSOCIATED(tree%ll)) CALL post_order_tree_evaluation2(tree%ll)
    IF(ASSOCIATED(tree%rl)) CALL post_order_tree_evaluation2(tree%rl)

    SELECT CASE (TRIM(tree%charvalue))
        CASE ("+")
            tree%charvalue = toChar(toNum(tree%ll%charvalue) + &
            toNum(tree%rl%charvalue))
            WRITE(*, "(A)", ADVANCE='no') TRIM(tree%charvalue) // ", "
        CASE ("-")
            tree%charvalue = toChar(toNum(tree%ll%charvalue) - &
            toNum(tree%rl%charvalue))
            WRITE(*, "(A)", ADVANCE='no') TRIM(tree%charvalue) // ", "
        CASE ("*")
            tree%charvalue = toChar(toNum(tree%ll%charvalue) * &
            toNum(tree%rl%charvalue))
            WRITE(*, "(A)", ADVANCE='no') TRIM(tree%charvalue) // ", "
        CASE ("/")
            tree%charvalue = toChar(toNum(tree%ll%charvalue) / &
            toNum(tree%rl%charvalue))
            WRITE(*, "(A)", ADVANCE='no') TRIM(tree%charvalue) // ", "
        CASE ("$")
            tree%charvalue = toChar(toNum(tree%ll%charvalue) ** &
            toNum(tree%rl%charvalue))
            WRITE(*, "(A)", ADVANCE='no') TRIM(tree%charvalue) // ", "
    END SELECT

    NULLIFY(tree%rl)
    NULLIFY(tree%ll)
END SUBROUTINE post_order_tree_evaluation2

Thanks!

keenerd · 2010-05-02 10:24:14

Sounds kind of like a homework problem :-)

In a general sense, you need to make a structure that holds the state and keep looping over the structure. Each pass of the loop pushes the structure a bit more towards the final goal. I've got an example (in python) of iteratively walking trees/graphs, both breadth first and depth first: http://kmkeen.com/python-trees/

Kiwi · 2010-05-02 15:06:31

While it is code from a homework assignment, the requirements do not include that they be in an iterative form, so the requirements are met already.

I am doing it to try and learn more and get better.

That, or I am a bigger masochist than I already thought.

raf_kig · 2010-05-06 02:37:26

Btw, when I was on the train last morning I did a rough python implementation of an iterative parser.
It doesn't cope with multi-digit literals, but it should give you a rough idea on how to do it.
(No guarantees though, was a fast hack and might not be correct ;-))

ops = ['+', '-', '/', '*', '$']

class Node:
    def __init__(self, val, depth=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.depth = depth
    def __repr__(self):
        if self.left or self.right:
            return '(%s%s%s)' % (self.left, self.val, self.right)
        else:
            return '%s' % (self.val)

def parse_tree(repr):
    depth = 0
    exprs = []
    for c in repr:
        if c == '(':
            depth += 1
        elif c == ')':
            depth -= 1
            #merge matching expressions
            if len(exprs) > 1 and exprs[-2].depth == depth:
                exprs[-1].right = exprs.pop(-1)

        #an operator, make it a node and make the expression to our left it's child
        elif c in ops:
            n = Node(c, depth=depth, left=exprs[-1])
            exprs[-1] = n
        #a literal, same depth as the operator before us -> make it it's child
        elif exprs and exprs[-1].depth == depth:
            exprs[-1].right = Node(c, depth=depth)
        #a literal, different depth than operator to the left / first expression
        else:
            exprs.append(Node(c, depth=depth))
    return exprs[0]



for a in ['((7+4)+(3/(4$(3-(9/8)))))', '((((5+3)/4)$2)+(((5-3)$2)/4))','((5-(2$(2$(1-(5*2)))))+(((((5-3)/6)$2)*4)/8))']:
    print a == str(parse_tree(a))

kpiche · 2010-05-08 03:25:19

You need something similar to operator precedence parsing.

Take two stacks, one to defer operators and one for output. As you traverse your expression push terms onto the output stack and save operators onto the operator stack *if* the top of the op stack doesn't have higher precedence that the current op. Otherwise pop higher precedence ops off the op stack and onto the output stack then push the current op onto op stack. After traversal pop all remaining ops and push them onto the output stack. The output stack resembles a postfix expression when done.

Parentheses require slight differences. When you see ')' move operators to the output until a '(', neither should be put in the output and ')' never gets on the op stack.

Since postfix stacks and trees are conceptually the same I leave it to you build an output tree instead of a stack.

Arch Linux

#1 2010-05-02 05:26:14

Convert recursive functions to iterative ones

#2 2010-05-02 10:24:14

Re: Convert recursive functions to iterative ones

#3 2010-05-02 15:06:31

Re: Convert recursive functions to iterative ones

#4 2010-05-06 02:37:26

Re: Convert recursive functions to iterative ones

#5 2010-05-08 03:25:19

Re: Convert recursive functions to iterative ones

Board footer