用c/c++输入一个中缀表达式，利用栈结构求解表达式的值

好的，这是一个经典的算法问题。首先，我们需要将中缀表达式转换为后缀表达式，然后再利用栈结构求解后缀表达式的值。具体的实现方法可以参考以下步骤：

1. 创建一个栈，用于存储操作符和操作数。
2. 从左到右遍历中缀表达式的每个字符。
3. 如果当前字符是数字，则将其压入栈中。
4. 如果当前字符是操作符，则将其与栈顶的操作符进行比较，如果当前操作符的优先级小于等于栈顶操作符的优先级，则将栈顶操作符弹出并计算，直到当前操作符的优先级大于栈顶操作符的优先级，然后将当前操作符压入栈中。
5. 如果当前字符是左括号，则将其压入栈中。
6. 如果当前字符是右括号，则弹出栈顶操作符并计算，直到遇到左括号为止。
7. 遍历完整个中缀表达式后，将栈中剩余的操作符依次弹出并计算，直到栈为空。

这样就可以得到后缀表达式了，然后再利用栈结构求解后缀表达式的值。具体的实现方法可以参考以下步骤：

1. 创建一个栈，用于存储操作数。
2. 从左到右遍历后缀表达式的每个字符。
3. 如果当前字符是数字，则将其压入栈中。
4. 如果当前字符是操作符，则从栈中弹出两个操作数，进行计算，并将计算结果压入栈中。
5. 遍历完整个后缀表达式后，栈中剩余的操作数就是表达式的值。

以上就是利用栈结构求解中缀表达式的值的具体实现方法。希望能对你有所帮助。

相关问题

用C/C++实现中缀表达式求值的算法

下面是一种用C语言实现中缀表达式求值的算法：

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

#define MAX_SIZE 100

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

int is_empty(Stack *s) {
    return s->top == -1;
}

int is_full(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int value) {
    if (is_full(s)) {
        printf("Stack is full.\n");
        exit(1);
    }
    s->top++;
    s->data[s->top] = value;
}

int pop(Stack *s) {
    if (is_empty(s)) {
        printf("Stack is empty.\n");
        exit(1);
    }
    int value = s->data[s->top];
    s->top--;
    return value;
}

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

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

int evaluate(int op1, int op2, char op) {
    switch (op) {
        case '+':
            return op1 + op2;
        case '-':
            return op1 - op2;
        case '*':
            return op1 * op2;
        case '/':
            return op1 / op2;
        default:
            return 0;
    }
}

int infix_to_postfix(char *infix, char *postfix) {
    int i, j;
    Stack s;
    s.top = -1;
    for (i = 0, j = 0; infix[i] != '\0'; i++) {
        if (isdigit(infix[i])) {
            postfix[j++] = infix[i];
        } else if (infix[i] == '(') {
            push(&s, infix[i]);
        } else if (infix[i] == ')') {
            while (!is_empty(&s) && peek(&s) != '(') {
                postfix[j++] = pop(&s);
            }
            if (is_empty(&s)) {
                printf("Invalid expression.\n");
                exit(1);
            }
            pop(&s);
        } else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
            while (!is_empty(&s) && peek(&s) != '(' && priority(infix[i]) <= priority(peek(&s))) {
                postfix[j++] = pop(&s);
            }
            push(&s, infix[i]);
        } else {
            printf("Invalid character: %c\n", infix[i]);
            exit(1);
        }
    }
    while (!is_empty(&s)) {
        if (peek(&s) == '(') {
            printf("Invalid expression.\n");
            exit(1);
        }
        postfix[j++] = pop(&s);
    }
    postfix[j] = '\0';
    return j;
}

int evaluate_postfix(char *postfix) {
    int i;
    Stack s;
    s.top = -1;
    for (i = 0; postfix[i] != '\0'; i++) {
        if (isdigit(postfix[i])) {
            push(&s, postfix[i] - '0');
        } else if (postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/') {
            int op2 = pop(&s);
            int op1 = pop(&s);
            int result = evaluate(op1, op2, postfix[i]);
            push(&s, result);
        } else {
            printf("Invalid character: %c\n", postfix[i]);
            exit(1);
        }
    }
    if (s.top != 0) {
        printf("Invalid expression.\n");
        exit(1);
    }
    return pop(&s);
}

int main() {
    char infix[MAX_SIZE], postfix[MAX_SIZE];
    printf("Enter an infix expression: ");
    fgets(infix, MAX_SIZE, stdin);
    infix[strcspn(infix, "\n")] = '\0';
    int length = infix_to_postfix(infix, postfix);
    printf("Postfix expression: %s\n", postfix);
    int result = evaluate_postfix(postfix);
    printf("Result: %d\n", result);
    return 0;
}

该算法使用两个栈，一个用于转换中缀表达式为后缀表达式，另一个用于求解后缀表达式。其中，转换中缀表达式为后缀表达式的过程中，遇到操作数直接输出到后缀表达式中，遇到左括号直接压入栈中，遇到右括号则将栈中元素弹出直到遇到左括号，并将左右括号都丢弃。遇到操作符时，如果栈顶元素为左括号，则直接将操作符压入栈中；否则，将栈中优先级大于等于当前操作符的元素都弹出，直到栈为空或栈顶元素为左括号，并将当前操作符压入栈中。转换完成后，如果栈中还有元素，则依次弹出并输出到后缀表达式中。

求解后缀表达式的过程中，遇到操作数则直接压入栈中，遇到操作符则弹出栈顶的两个元素作为操作数，计算结果并将结果压入栈中。最终，如果栈中只有一个元素，则该元素即为表达式的值。如果栈中元素多于一个，则表明表达式有误。

输入一个中缀算术表达式，求解表达式的值。运算符包括+、-、*、/、(、)、=，使用c++编写代码

我可以为您提供一个简单的中缀表达式求解程序，以下是使用C语言编写的代码：

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

#define STACK_SIZE 50

// 符号栈结构体
struct stack {
    int items[STACK_SIZE];
    int top;
};

// 初始化符号栈
void init_stack(struct stack *s) {
    s->top = -1;
}

// 判断符号栈是否为空
int is_empty(struct stack *s) {
    return s->top == -1;
}

// 判断符号栈是否已满
int is_full(struct stack *s) {
    return s->top == STACK_SIZE - 1;
}

// 入栈操作
void push(struct stack *s, int item) {
    if (is_full(s)) {
        printf("\nStack is full!");
        exit(1);
    }
    s->items[++s->top] = item;
}

// 出栈操作
int pop(struct stack *s) {
    if (is_empty(s)) {
        printf("\nInvalid expression!");
        exit(1);
    }
    return s->items[s->top--];
}

// 获取栈顶元素
int peek(struct stack *s) {
    if (is_empty(s)) {
        printf("\nInvalid expression!");
        exit(1);
    }
    return s->items[s->top];
}

// 判断是否为操作符
int is_operator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')');
}

// 判断操作符的优先级
int precedence(char c) {
    if (c == '(' || c == ')') {
        return 0;
    }
    if (c == '+' || c == '-') {
        return 1;
    }
    if (c == '*' || c == '/') {
        return 2;
    }
    return 0;
}

// 运算操作
int operate(int op1, int op2, char operator) {
    switch (operator) {
        case '+':
            return op1 + op2;
        case '-':
            return op1 - op2;
        case '*':
            return op1 * op2;
        case '/':
            return op1 / op2;
    }
    return 0;
}

// 解析中缀表达式
int evaluate(char *expression) {
    struct stack operand_stack, operator_stack;
    int i, n, operand1, operand2;
    char token, operator;
    init_stack(&operand_stack);
    init_stack(&operator_stack);

    n = strlen(expression);
    for (i = 0; i < n; i++) {
        token = expression[i];
        // 如果是数字，压入操作数栈
        if (isdigit(token)) {
            push(&operand_stack, token - '0');
        }
        // 如果是左括号，压入操作符栈
        else if (token == '(') {
            push(&operator_stack, token);
        }
        // 如果是右括号，将操作符栈中左括号之间的操作符依次弹出，并进行运算，最后将左括号弹出
        else if (token == ')') {
            while (peek(&operator_stack) != '(') {
                operand2 = pop(&operand_stack);
                operand1 = pop(&operand_stack);
                operator = pop(&operator_stack);
                push(&operand_stack, operate(operand1, operand2, operator));
            }
            pop(&operator_stack);
        }
        // 如果是操作符，需要进行进一步判断
        else if (is_operator(token)) {
            // 如果当前操作符优先级小于等于操作符栈顶的操作符，将操作符栈顶的操作符依次弹出，并进行运算
            while (!is_empty(&operator_stack) && precedence(token) <= precedence(peek(&operator_stack))) {
                operand2 = pop(&operand_stack);
                operand1 = pop(&operand_stack);
                operator = pop(&operator_stack);
                push(&operand_stack, operate(operand1, operand2, operator));
            }
            // 将当前操作符压入操作符栈
            push(&operator_stack, token);
        }
    }

    // 处理剩余的操作符
    while (!is_empty(&operator_stack)) {
        operand2 = pop(&operand_stack);
        operand1 = pop(&operand_stack);
        operator = pop(&operator_stack);
        push(&operand_stack, operate(operand1, operand2, operator));
    }

    // 返回最终结果
    return pop(&operand_stack);
}

int main() {
    char expression[50];
    int result;

    printf("Please input an infix arithmetic expression:\n");
    scanf("%s", expression);

    result = evaluate(expression);

    printf("\nResult = %d", result);

    return 0;
}

使用该程序求解中缀表达式的值时，需要注意输入表达式时需用括号括起来，例如：(1+2)*3。