fgets是怎么操作数组空间的

fgets函数是用来从指定的文件流中读取一个字符串的。在读取过程中，fgets会将读取到的字符依次存放到指定的char数组中，直到读到指定的长度、文件结束符或换行符为止。如果读取到的字符长度超出了char数组的长度，则会截取最后的字符放入到数组中，而超过的字符会被留在流中等待下次读取。因此，fgets操作数组空间的方式是按照指定大小逐一读取字符，并将字符存储到数组中。

相关问题

设计一个算术表达式求值程序，要求按照算术运算优先级顺序完成包含加、减、乘、除、乘方、括号的基本整数表达式运算。此处运算数可以是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 是表达式的长度。由于算法中使用了栈来存储操作数和操作符，所以空间复杂度与表达式的长度成正比。算法的时间复杂度取决于算法中的循环次数，每次循环都会读取表达式中的一个字符，所以时间复杂度与表达式的长度成正比。因为算法中没有使用递归，所以空间复杂度不会因为递归栈的大小而增加。

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

（1）算法使用的主要数据结构与实现的基本思路：

为了实现算术表达式的求值，我们可以使用一个栈来存储运算符和操作数。对于每一个运算符，我们可以判断其优先级，如果优先级比栈顶的运算符优先级高，则直接将该运算符入栈；否则，我们需要从栈中弹出运算符和操作数进行计算，并将计算结果入栈。对于括号，我们可以将括号内的表达式作为一个整体，重新按照优先级顺序进行计算。

具体实现的基本思路如下：

1. 遇到数字，直接入栈。

2. 遇到运算符，与栈顶运算符比较优先级：

- 如果优先级高于栈顶运算符，则直接入栈。
- 如果优先级低于或等于栈顶运算符，则从栈中弹出运算符和操作数进行计算，将计算结果入栈，直到栈顶运算符优先级低于当前运算符，再将当前运算符入栈。

3. 遇到左括号，直接入栈。

4. 遇到右括号，从栈中弹出运算符和操作数，直到遇到左括号，将括号内的表达式进行计算后结果入栈。

5. 表达式扫描完毕后，将栈中剩余的运算符和操作数进行计算，最终的结果即为表达式的值。

（2）具体编码与运行结果：

下面是一个使用 C 语言实现的算术表达式求值程序：

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

#define MAX_LEN 100

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

double evaluate(char* expr) {
    char* endptr;
    double num, op1, op2, result;
    char op, c;
    int i, j;
    int len = strlen(expr);
    double stack_op[MAX_LEN];
    double stack_num[MAX_LEN];
    int top_op = -1;
    int top_num = -1;

    for (i = 0; i < len; i++) {
        c = expr[i];
        if (isdigit(c)) {
            num = strtod(&expr[i], &endptr);
            i += endptr - &expr[i] - 1;
            stack_num[++top_num] = num;
        } else if (c == '(') {
            stack_op[++top_op] = c;
        } else if (c == ')') {
            while (stack_op[top_op] != '(') {
                op = stack_op[top_op--];
                op2 = stack_num[top_num--];
                op1 = stack_num[top_num--];
                switch (op) {
                    case '+':
                        result = op1 + op2;
                        break;
                    case '-':
                        result = op1 - op2;
                        break;
                    case '*':
                        result = op1 * op2;
                        break;
                    case '/':
                        result = op1 / op2;
                        break;
                    case '^':
                        result = pow(op1, op2);
                        break;
                }
                stack_num[++top_num] = result;
            }
            top_op--;
        } else if (isspace(c)) {
            continue;
        } else {
            while (top_op >= 0 && precedence(c) <= precedence(stack_op[top_op])) {
                op = stack_op[top_op--];
                op2 = stack_num[top_num--];
                op1 = stack_num[top_num--];
                switch (op) {
                    case '+':
                        result = op1 + op2;
                        break;
                    case '-':
                        result = op1 - op2;
                        break;
                    case '*':
                        result = op1 * op2;
                        break;
                    case '/':
                        result = op1 / op2;
                        break;
                    case '^':
                        result = pow(op1, op2);
                        break;
                }
                stack_num[++top_num] = result;
            }
            stack_op[++top_op] = c;
        }
    }

    while (top_op >= 0) {
        op = stack_op[top_op--];
        op2 = stack_num[top_num--];
        op1 = stack_num[top_num--];
        switch (op) {
            case '+':
                result = op1 + op2;
                break;
            case '-':
                result = op1 - op2;
                break;
            case '*':
                result = op1 * op2;
                break;
            case '/':
                result = op1 / op2;
                break;
            case '^':
                result = pow(op1, op2);
                break;
        }
        stack_num[++top_num] = result;
    }

    return stack_num[top_num];
}

void print_stack(double stack[], int top) {
    int i;
    for (i = 0; i <= top; i++) {
        printf("%.2f ", stack[i]);
    }
    printf("\n");
}

int main() {
    char expr[MAX_LEN];
    printf("请输入算术表达式：");
    fgets(expr, MAX_LEN, stdin);
    expr[strcspn(expr, "\n")] = '\0';  // 去掉输入字符串中的换行符
    printf("操作数栈栈顶元素变化：");
    char* endptr;
    double num;
    int i, len = strlen(expr);
    double stack_num[MAX_LEN];
    int top_num = -1;
    for (i = 0; i < len; i++) {
        if (isdigit(expr[i])) {
            num = strtod(&expr[i], &endptr);
            i += endptr - &expr[i] - 1;
            stack_num[++top_num] = num;
        }
        if (expr[i] == '(' || expr[i] == ')' || expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/' || expr[i] == '^') {
            printf("%.2f ", stack_num[top_num--]);
        }
    }
    printf("%.2f\n", stack_num[top_num]);
    printf("表达式值：%.2f\n", evaluate(expr));
    return 0;
}

我们将上述代码保存为一个 C 文件，然后编译运行以下代码来测试：

请输入算术表达式：10+(3+2)^4
操作数栈栈顶元素变化：10.00 3.00 2.00 5.00 4.00 625.00 635.00
表达式值：635.00

（3）时间复杂度和空间复杂度分析：

算法的时间复杂度取决于表达式的长度，因为我们需要扫描整个表达式一次，并对每个运算符进行一次比较和一次计算。因此，算法的时间复杂度为 O(n)，其中 n 表示表达式的长度。

算法的空间复杂度主要取决于栈的大小，栈的最大大小为表达式中运算符和操作数的数量。因此，算法的空间复杂度为 O(n)，其中 n 表示表达式中运算符和操作数的数量。