<SYSTEM_TASK:>
Solve the following problem using Python, implementing the functions described below, one line at a time
<END_TASK>
<USER_TASK:>
Description:
 def substitute(s, objlist=(), globals={}, locals={}):
 """Substitute global python variables in a command string. This function parses a string and tries to substitute parts like `$name` by their value. It is uses by :mod:`image` and :mod:`table` to handle image and table objects in a command, but also other variables (integers, strings, etc.) can be substituted. The following rules apply: 1. A name must start with an underscore or alphabetic, followed by zero or more alphanumerics and underscores. 2. String parts enclosed in single or double quotes are literals and are left untouched. Furthermore a $ can be escaped by a backslash, which is useful if an environment variable is used. Note that an extra backslash is required in Python to escape the backslash. The output contains the quotes and backslashes. 3. A variable is looked up in the given local and global namespaces. 4. If the variable `name` has a vector value, its substitution is enclosed in square brackets and separated by commas. 5. A string value is enclosed in double quotes. If the value contains a double quote, that quote is enclosed in single quotes. 6. If the name's value has a type mentioned in the argument `objlist`, it is substituted by `$n` (where n is a sequence number) and its value is added to the objects of that type in `objlist`. 7. If the name is unknown or has an unknown type, it is left untouched. The `objlist` argument is a list of tuples or lists where each tuple or list has three fields: 1. The first field is the object type (e.g. `table`) 2. The second field is a prefix for the sequence number (usually empty). E.g. regions could have prefix 'r' resulting in a substitution like `$r1`. 3. The third field is a list of objects to be substituted. New objects get appended to it. Usually the list is initially empty. Apart from substituting variables, it also substitutes `$(expression)` by the expression result. It correctly handles parentheses and quotes in the expression. For example:: '5+2' '7' '$((a+b)+$a)' '25' '9' Substitution is NOT recursive. E.g. if a=1 and b="$a", the result of substitute("$b") is "$a" and not 1. """

    # Get the local variables at the caller level if not given.
    if not locals:
        locals = getlocals(3)
    # Initialize some variables.
    backslash = False
    dollar = False
    nparen = 0
    name = ''
    evalstr = ''
    squote = False
    dquote = False
    out = ''
    # Loop through the entire string.
    for tmp in s:
        if backslash:
            out += tmp
            backslash = False
            continue
        # If a dollar is found, we might have a name or expression.
        # Alphabetics and underscore are always part of name.
        if dollar and nparen == 0:
            if tmp == '_' or ('a' <= tmp <= 'z') or ('A' <= tmp <= 'Z'):
                name += tmp
                continue
            # Numerics are only part if not first character.
            if '0' <= tmp <= '9' and name != '':
                name += tmp
                continue
            # $( indicates the start of an expression to evaluate.
            if tmp == '(' and name == '':
                nparen = 1
                evalstr = ''
                continue
            # End of name found. Try to substitute.
            out += substitutename(name, objlist, globals, locals)
            dollar = False

        # Handle possible single or double quotes.
        if tmp == '"' and not squote:
            dquote = not dquote
        elif tmp == "'" and not dquote:
            squote = not squote
        if not dquote and not squote:
            # Count the number of balanced parentheses
            # (outside quoted strings) in the subexpression.
            if nparen > 0:
                if tmp == '(':
                    nparen += 1
                elif tmp == ')':
                    nparen -= 1
                    if nparen == 0:
                        # The last closing parenthese is found.
                        # Evaluate the subexpression.
                        # Add the result to the output.
                        out += substituteexpr(evalstr, globals, locals)
                        dollar = False
                evalstr += tmp
                continue
            # Set a switch if we have a dollar (outside quoted
            # and eval strings).
            if tmp == '$':
                dollar = True
                name = ''
                continue
        # No special character; add it to output or evalstr.
        # Set a switch if we have a backslash.
        if nparen == 0:
            out += tmp
        else:
            evalstr += tmp
        if tmp == '\\':
            backslash = True

        # The entire string has been handled.
        # Substitute a possible last name.
        # Insert a possible incomplete eval string as such.
    if dollar:
        out += substitutename(name, objlist, globals, locals)
    else:
        if nparen > 0:
            out += '$(' + evalstr
    return out