设计一个算术表达式求值程序，要求按照算术运算优先级顺序完成包含加、减、乘、除、乘方、括号的基本整数表达式运算。此处运算数可以是1位长度，也可以是多位长度。输入表达式后依次输出在求值过程中运算数栈内的栈顶数据变化过程，并最终输出表达式值。 例如： 输入： 10+(3+2)^4 输出： 操作数栈栈顶元素变化： 10 3 2 5 4 625 635 表达式值：635 要求：（1）阐述算法使用的主要数据结构与实现的基本思路； （2）给出具体编码与运行结果； （3）请分析算法时间复杂度和空间复杂度。

算法使用的主要数据结构是栈，基本思路如下：

1. 定义两个栈，一个操作数栈，一个操作符栈。
2. 从左到右扫描表达式，遇到数字直接入操作数栈，遇到操作符则与操作符栈顶元素比较优先级，如果当前操作符的优先级大于栈顶元素的优先级，则直接入栈，否则将操作符栈栈顶元素弹出，与操作数栈栈顶的两个元素进行运算，将结果入操作数栈，直到当前操作符可以入栈为止。
3. 当表达式扫描完毕后，依次取出操作符栈中的元素与操作数栈中的元素进行运算，直到操作符栈为空。
4. 最终操作数栈中的元素就是表达式的值。

具体编码如下（使用Python语言）：

class Stack:
    def __init__(self):
        self.items = []
    
    def is_empty(self):
        return self.items == []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[-1]
    
    def size(self):
        return len(self.items)

def evaluate(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    operand_stack = Stack()
    operator_stack = Stack()
    index = 0
    
    while index < len(expression):
        token = expression[index]
        
        if token.isdigit():
            start = index
            while index < len(expression) and expression[index].isdigit():
                index += 1
            operand_stack.push(int(expression[start:index]))
            continue
        
        if token in precedence:
            while not operator_stack.is_empty() and precedence[operator_stack.peek()] >= precedence[token]:
                right_operand = operand_stack.pop()
                left_operand = operand_stack.pop()
                operator = operator_stack.pop()
                result = calculate(left_operand, right_operand, operator)
                operand_stack.push(result)
            
            operator_stack.push(token)
        
        elif token == '(':
            operator_stack.push(token)
        
        elif token == ')':
            while operator_stack.peek() != '(':
                right_operand = operand_stack.pop()
                left_operand = operand_stack.pop()
                operator = operator_stack.pop()
                result = calculate(left_operand, right_operand, operator)
                operand_stack.push(result)
            operator_stack.pop()
        
        index += 1
    
    while not operator_stack.is_empty():
        right_operand = operand_stack.pop()
        left_operand = operand_stack.pop()
        operator = operator_stack.pop()
        result = calculate(left_operand, right_operand, operator)
        operand_stack.push(result)
    
    return operand_stack.pop()

def calculate(left_operand, right_operand, operator):
    if operator == '+':
        return left_operand + right_operand
    elif operator == '-':
        return left_operand - right_operand
    elif operator == '*':
        return left_operand * right_operand
    elif operator == '/':
        return left_operand / right_operand
    elif operator == '^':
        return left_operand ** right_operand

expression = "10+(3+2)^4"
operand_stack = Stack()
operator_stack = Stack()
index = 0

print("操作数栈栈顶元素变化：")
while index < len(expression):
    token = expression[index]
        
    if token.isdigit():
        start = index
        while index < len(expression) and expression[index].isdigit():
            index += 1
        operand_stack.push(int(expression[start:index]))
        print(operand_stack.items[-1])
        continue
        
    if token in precedence:
        while not operator_stack.is_empty() and precedence[operator_stack.peek()] >= precedence[token]:
            right_operand = operand_stack.pop()
            left_operand = operand_stack.pop()
            operator = operator_stack.pop()
            result = calculate(left_operand, right_operand, operator)
            operand_stack.push(result)
            print(operand_stack.items[-1])
        
        operator_stack.push(token)
        
    elif token == '(':
        operator_stack.push(token)
        
    elif token == ')':
        while operator_stack.peek() != '(':
            right_operand = operand_stack.pop()
            left_operand = operand_stack.pop()
            operator = operator_stack.pop()
            result = calculate(left_operand, right_operand, operator)
            operand_stack.push(result)
            print(operand_stack.items[-1])
        operator_stack.pop()
        
    index += 1
    
while not operator_stack.is_empty():
    right_operand = operand_stack.pop()
    left_operand = operand_stack.pop()
    operator = operator_stack.pop()
    result = calculate(left_operand, right_operand, operator)
    operand_stack.push(result)
    print(operand_stack.items[-1])

print("表达式值：", operand_stack.pop())

运行结果如下：

操作数栈栈顶元素变化：
10
3
2
5
4
625
635
表达式值： 635

算法时间复杂度为O(n)，其中n为表达式的长度，因为每个字符只会被扫描一次。算法空间复杂度取决于操作数和操作符的个数，最坏情况下可能需要使用两个栈，因此空间复杂度为O(n)。