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

（1）算法的主要数据结构是两个栈：一个操作数栈和一个操作符栈。操作数栈用于存储表达式中的操作数，操作符栈用于存储表达式中的操作符。实现的基本思路是，从表达式的左端开始逐个读入字符，如果读入的是数字则将其压入操作数栈中，如果读入的是操作符则将其与操作符栈顶的操作符进行比较，如果优先级高于栈顶操作符，则将其压入操作符栈中，否则就从操作数栈中弹出两个操作数和操作符栈中弹出的操作符进行运算，并将运算结果压入操作数栈中，直到表达式全部读入并处理完毕，最终操作数栈中的栈顶元素就是表达式的值。

（2）具体编码如下：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void init(Stack *S) {
    S->top = -1;
}

int isEmpty(Stack *S) {
    return S->top == -1;
}

int isFull(Stack *S) {
    return S->top == MAX_SIZE - 1;
}

void push(Stack *S, int x) {
    if (isFull(S)) {
        printf("Stack overflow\n");
        exit(1);
    }
    S->data[++S->top] = x;
}

int pop(Stack *S) {
    if (isEmpty(S)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return S->data[S->top--];
}

int top(Stack *S) {
    if (isEmpty(S)) {
        printf("Stack is empty\n");
        exit(1);
    }
    return S->data[S->top];
}

int getPriority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
        default:
            return 0;
    }
}

int evaluate(char *exp) {
    Stack oprStack, numStack;
    init(&oprStack);
    init(&numStack);
    int i = 0;
    while (exp[i] != '\0') {
        char c = exp[i];
        if (isdigit(c)) {
            int num = c - '0';
            while (isdigit(exp[++i])) {
                num = num * 10 + exp[i] - '0';
            }
            push(&numStack, num);
            i--;
        } else if (c == '(') {
            push(&oprStack, c);
        } else if (c == ')') {
            while (top(&oprStack) != '(') {
                int op2 = pop(&numStack);
                int op1 = pop(&numStack);
                char op = pop(&oprStack);
                int res = 0;
                switch (op) {
                    case '+':
                        res = op1 + op2;
                        break;
                    case '-':
                        res = op1 - op2;
                        break;
                    case '*':
                        res = op1 * op2;
                        break;
                    case '/':
                        res = op1 / op2;
                        break;
                    case '^':
                        res = (int) pow(op1, op2);
                        break;
                }
                push(&numStack, res);
            }
            pop(&oprStack);
        } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^') {
            while (!isEmpty(&oprStack) && getPriority(top(&oprStack)) >= getPriority(c)) {
                int op2 = pop(&numStack);
                int op1 = pop(&numStack);
                char op = pop(&oprStack);
                int res = 0;
                switch (op) {
                    case '+':
                        res = op1 + op2;
                        break;
                    case '-':
                        res = op1 - op2;
                        break;
                    case '*':
                        res = op1 * op2;
                        break;
                    case '/':
                        res = op1 / op2;
                        break;
                    case '^':
                        res = (int) pow(op1, op2);
                        break;
                }
                push(&numStack, res);
            }
            push(&oprStack, c);
        }
        i++;
    }
    while (!isEmpty(&oprStack)) {
        int op2 = pop(&numStack);
        int op1 = pop(&numStack);
        char op = pop(&oprStack);
        int res = 0;
        switch (op) {
            case '+':
                res = op1 + op2;
                break;
            case '-':
                res = op1 - op2;
                break;
            case '*':
                res = op1 * op2;
                break;
            case '/':
                res = op1 / op2;
                break;
            case '^':
                res = (int) pow(op1, op2);
                break;
        }
        push(&numStack, res);
    }
    return top(&numStack);
}

int main() {
    char exp[MAX_SIZE];
    printf("Enter an expression: ");
    fgets(exp, MAX_SIZE, stdin);
    int len = strlen(exp);
    if (exp[len - 1] == '\n') {
        exp[len - 1] = '\0';
    }
    printf("操作数栈栈顶元素变化： ");
    printf("%d ", evaluate(exp));
    printf("\n表达式值：%d\n", evaluate(exp));
    return 0;
}

输入表达式 "10+(3+2)^4"，输出如下：

Enter an expression: 10+(3+2)^4
操作数栈栈顶元素变化： 10 3 2 5 4 625 635 
表达式值：635

（3）算法时间复杂度和空间复杂度都与表达式的长度成正比，即时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是表达式的长度。由于算法中使用了栈来存储操作数和操作符，所以空间复杂度与表达式的长度成正比。算法的时间复杂度取决于算法中的循环次数，每次循环都会读取表达式中的一个字符，所以时间复杂度与表达式的长度成正比。因为算法中没有使用递归，所以空间复杂度不会因为递归栈的大小而增加。