Python 2 or 3.

Using deque for O(1) left/right append/pop, and also because it makes the code somewhat symmetrical for left/right associativity.

If you prefer (reverse-)Polish notation, add/remove a # at the beginning of the program.

from collections import deque

# choose the notation you like:
# formatting = lambda l, o, r: '{} {} {}'.format(l, r, o)  # reverse Polish
# formatting = lambda l, o, r: '{} {} {}'.format(o, l, r)  # Polish
formatting = lambda l, o, r: '({}{}{})'.format(l, o, r)  # usual


def solve(text):
    lines = iter(text.split('\n'))
    operators = []
    for _ in range(int(next(lines))):
        operator, associativity = next(lines).split(':')
        operators.append((operator, associativity == 'left'))
    return flatten(iter(next(lines)), operators)


def flatten(iterator, operators):
    parts = deque()
    # handle brackets
    for t in iterator:
        if t == '(':
            parts.append(flatten(iterator, operators))
        elif t == ')':
            break
        else:
            parts.append(t)
    # flatten each operator
    for operator, left_associative in operators:
        new_parts = deque()
        new_parts.append(parts.popleft() if left_associative else parts.pop())
        while parts:
            part = parts.popleft() if left_associative else parts.pop()
            if part == operator:
                if left_associative:
                    part = formatting(new_parts.pop(), part, parts.popleft())
                else:
                    part = formatting(parts.pop(), part, new_parts.popleft())
            if left_associative:
                new_parts.append(part)
            else:
                new_parts.appendleft(part)
        parts = new_parts
    assert len(parts) == 1  # >1 if unknown operator, wrong input...
    return parts.pop()


if __name__ == '__main__':
    print (solve('3\n^:right\n*:left\n+:left\n1+2*(3+4)^5+6+7*8'))