表达式求值使用数据结构C语言

在C语言中，表达式求值可以使用数据结构来实现。常用的数据结构包括栈和队列。

1. 使用栈：
表达式求值中最常用的数据结构是栈。栈是一种后进先出（LIFO）的数据结构，可以用来保存运算符和操作数。
- 遍历表达式，遇到操作数时，将其入栈。
- 遇到运算符时，与栈顶运算符进行比较，如果栈顶运算符优先级较高，则将栈顶运算符出栈并进行计算，然后将计算结果入栈。
- 如果栈顶运算符优先级较低或相等，则将当前运算符入栈。
- 当表达式遍历完毕后，将栈中剩余的运算符依次出栈并进行计算，直到栈为空。

2. 使用队列：
另一种实现表达式求值的数据结构是队列。队列是一种先进先出（FIFO）的数据结构，可以用来保存操作数和运算符。
- 遍历表达式，遇到操作数时，将其入队列。
- 遇到运算符时，与队列中的运算符进行比较，如果队列中的运算符优先级较高，则将队列中的运算符出队列并进行计算，然后将计算结果入队列。
- 如果队列中的运算符优先级较低或相等，则将当前运算符入队列。
- 当表达式遍历完毕后，将队列中剩余的运算符依次出队列并进行计算，直到队列为空。

相关问题

表达式求值数据结构 c语言

在 C 语言中，表达式求值可以使用栈这种数据结构来实现。具体步骤如下：

1. 定义两个栈：一个操作符栈和一个操作数栈。

2. 从左到右遍历表达式中的每一个元素（数字或者操作符）。

3. 如果当前元素是数字，就将它压入操作数栈。

4. 如果当前元素是操作符，就将它压入操作符栈。

5. 每当遇到一个操作符时，就从操作数栈中弹出两个元素，进行相应的计算，并将结果压入操作数栈。

6. 当遍历完整个表达式后，操作数栈中就只剩下一个元素，就是表达式的最终结果。

下面是一个简单的表达式求值的 C 语言代码实现：

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

#define STACK_SIZE 100

typedef enum {false, true} bool;

typedef struct {
    int top;
    char data[STACK_SIZE];
} OperatorStack;

typedef struct {
    int top;
    int data[STACK_SIZE];
} OperandStack;

void initOperatorStack(OperatorStack *s) {
    s->top = -1;
}

void initOperandStack(OperandStack *s) {
    s->top = -1;
}

bool isOperatorStackEmpty(OperatorStack *s) {
    return s->top == -1;
}

bool isOperandStackEmpty(OperandStack *s) {
    return s->top == -1;
}

bool isOperatorStackFull(OperatorStack *s) {
    return s->top == STACK_SIZE - 1;
}

bool isOperandStackFull(OperandStack *s) {
    return s->top == STACK_SIZE - 1;
}

void pushOperatorStack(OperatorStack *s, char c) {
    if (isOperatorStackFull(s)) {
        printf("Operator stack overflow!\n");
        exit(EXIT_FAILURE);
    }
    s->data[++s->top] = c;
}

void pushOperandStack(OperandStack *s, int n) {
    if (isOperandStackFull(s)) {
        printf("Operand stack overflow!\n");
        exit(EXIT_FAILURE);
    }
    s->data[++s->top] = n;
}

char popOperatorStack(OperatorStack *s) {
    if (isOperatorStackEmpty(s)) {
        printf("Operator stack underflow!\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top--];
}

int popOperandStack(OperandStack *s) {
    if (isOperandStackEmpty(s)) {
        printf("Operand stack underflow!\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top--];
}

int evaluate(char *expr) {
    OperatorStack opstack;
    OperandStack opndstack;
    char *p = expr;

    initOperatorStack(&opstack);
    initOperandStack(&opndstack);

    while (*p != '\0') {
        if (isdigit(*p)) {
            int n = 0;
            while (isdigit(*p)) {
                n = n * 10 + (*p - '0');
                p++;
            }
            pushOperandStack(&opndstack, n);
        } else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {
            while (!isOperatorStackEmpty(&opstack) && opstack.data[opstack.top] != '(' && (*p == '*' || *p == '/') <= (opstack.data[opstack.top] == '+' || opstack.data[opstack.top] == '-')) {
                int opnd2 = popOperandStack(&opndstack);
                int opnd1 = popOperandStack(&opndstack);
                char op = popOperatorStack(&opstack);
                switch (op) {
                    case '+':
                        pushOperandStack(&opndstack, opnd1 + opnd2);
                        break;
                    case '-':
                        pushOperandStack(&opndstack, opnd1 - opnd2);
                        break;
                    case '*':
                        pushOperandStack(&opndstack, opnd1 * opnd2);
                        break;
                    case '/':
                        pushOperandStack(&opndstack, opnd1 / opnd2);
                        break;
                }
            }
            pushOperatorStack(&opstack, *p);
            p++;
        } else if (*p == '(') {
            pushOperatorStack(&opstack, *p);
            p++;
        } else if (*p == ')') {
            while (opstack.data[opstack.top] != '(') {
                int opnd2 = popOperandStack(&opndstack);
                int opnd1 = popOperandStack(&opndstack);
                char op = popOperatorStack(&opstack);
                switch (op) {
                    case '+':
                        pushOperandStack(&opndstack, opnd1 + opnd2);
                        break;
                    case '-':
                        pushOperandStack(&opndstack, opnd1 - opnd2);
                        break;
                    case '*':
                        pushOperandStack(&opndstack, opnd1 * opnd2);
                        break;
                    case '/':
                        pushOperandStack(&opndstack, opnd1 / opnd2);
                        break;
                }
            }
            popOperatorStack(&opstack);
            p++;
        } else {
            p++;
        }
    }

    while (!isOperatorStackEmpty(&opstack)) {
        int opnd2 = popOperandStack(&opndstack);
        int opnd1 = popOperandStack(&opndstack);
        char op = popOperatorStack(&opstack);
        switch (op) {
            case '+':
                pushOperandStack(&opndstack, opnd1 + opnd2);
                break;
            case '-':
                pushOperandStack(&opndstack, opnd1 - opnd2);
                break;
            case '*':
                pushOperandStack(&opndstack, opnd1 * opnd2);
                break;
            case '/':
                pushOperandStack(&opndstack, opnd1 / opnd2);
                break;
        }
    }

    return popOperandStack(&opndstack);
}

int main() {
    char expr[100];
    printf("Enter an expression: ");
    scanf("%s", expr);
    int result = evaluate(expr);
    printf("Result: %d\n", result);
    return 0;
}

数据结构表达式求值，用C语言

表达式求值是计算机科学中一个十分重要的问题，可以用不同的数据结构实现。其中，最常用的数据结构是栈。

具体实现过程如下：

1. 定义一个栈，用来存储操作符和操作数。

2. 从左到右扫描表达式，遇到数字就入栈，遇到操作符就进行计算。

3. 当遇到操作符时，从栈中弹出两个操作数，进行计算，将结果重新入栈。

4. 当整个表达式扫描完毕后，栈中只剩下一个元素，即表达式的值。

下面是一个简单的表达式求值的 C 语言代码示例：

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

#define STACK_SIZE 100

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

int pop(Stack *s) {
    if (s->top < 0) {
        printf("Error: stack underflow\n");
        exit(1);
    }
    return s->data[s->top--];
}

void push(Stack *s, int value) {
    if (s->top >= STACK_SIZE - 1) {
        printf("Error: stack overflow\n");
        exit(1);
    }
    s->data[++s->top] = value;
}

int main() {
    Stack stack = { -1, { 0 } };
    char input[STACK_SIZE];
    int i = 0;

    printf("Enter an expression: ");
    scanf("%s", input);

    while (input[i]) {
        if (isdigit(input[i])) {
            push(&stack, input[i] - '0');
        } else {
            int right_operand = pop(&stack);
            int left_operand = pop(&stack);
            switch (input[i]) {
                case '+':
                    push(&stack, left_operand + right_operand);
                    break;
                case '-':
                    push(&stack, left_operand - right_operand);
                    break;
                case '*':
                    push(&stack, left_operand * right_operand);
                    break;
                case '/':
                    push(&stack, left_operand / right_operand);
                    break;
                default:
                    printf("Error: invalid operator '%c'\n", input[i]);
                    exit(1);
            }
        }
        i++;
    }

    printf("Result: %d\n", pop(&stack));

    return 0;
}

在上面的代码中，我们使用了一个结构体来表示栈，包含两个成员：栈顶指针和数据数组。我们还定义了两个函数来实现入栈和出栈操作。

在主函数中，我们首先读入一个表达式，然后逐个字符地扫描它。如果遇到数字，就将它转换为整数并入栈；如果遇到操作符，就弹出栈顶的两个操作数，进行计算，并将结果入栈。最后，栈中只剩下一个元素，它就是表达式的值。