用栈实现算数表达式的求值

好的，这是一个计算机科学问题，非常适合我作为AI进行回答。使用栈可以方便地实现算术表达式的求值。具体实现方式为：将中缀表达式转换成后缀表达式，在栈中使用一个运算符栈和一个操作数栈，扫描后缀表达式，遇到操作数则入栈，遇到运算符则弹出操作数，进行运算后将结果入栈，最后操作数栈中的唯一元素即为表达式的结果。

相关问题

C语言栈实现算数表达式求值代码

下面是一个基于C语言栈实现算数表达式求值的代码示例：

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

#define MAX_SIZE 100

// 定义栈的数据结构
typedef struct Stack {
    int top;         // 栈顶指针
    int data[MAX_SIZE];   // 存储数据的数组
} Stack;

// 初始化栈
void init(Stack *stack) {
    stack->top = -1;
}

// 判断栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

// 入栈
void push(Stack *stack, int item) {
    if (isFull(stack)) {
        printf("Stack Overflow.\n");
        exit(EXIT_FAILURE);
    }
    stack->data[++stack->top] = item;
}

// 出栈
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow.\n");
        exit(EXIT_FAILURE);
    }
    return stack->data[stack->top--];
}

// 取栈顶元素
int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow.\n");
        exit(EXIT_FAILURE);
    }
    return stack->data[stack->top];
}

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

// 获取操作符的优先级，返回值越大优先级越高
int getPriority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

// 对表达式进行求值
int evaluate(char *expression) {
    Stack operands, operators;
    int i, n, val, op1, op2;
    char ch, prev;

    // 初始化两个栈
    init(&operands);
    init(&operators);

    n = strlen(expression);
    prev = '\0';

    for (i = 0; i < n; i++) {
        ch = expression[i];

        // 如果是空白字符，则跳过
        if (isspace(ch)) {
            continue;
        }

        // 如果是数字，则将其入栈
        if (isdigit(ch)) {
            val = ch - '0';

            // 取多位数
            while (i + 1 < n && isdigit(expression[i + 1])) {
                val = val * 10 + (expression[++i] - '0');
            }

            // 如果前一个字符是')'，说明当前数字是括号内的第一个数，直接入栈
            // 否则，说明前一个数和当前数构成一位多位数，需要将其弹出并计算
            if (prev != ')') {
                op1 = pop(&operands);
                val = op1 * 10 + val;
            }

            push(&operands, val);
        }
        // 如果是'('，则直接入栈
        else if (ch == '(') {
            push(&operators, ch);
        }
        // 如果是')'，则将运算符栈中'('上面的所有运算符取出并计算
        else if (ch == ')') {
            while (peek(&operators) != '(') {
                op2 = pop(&operands);
                op1 = pop(&operands);
                val = pop(&operators);

                switch (val) {
                    case '+':
                        val = op1 + op2;
                        break;
                    case '-':
                        val = op1 - op2;
                        break;
                    case '*':
                        val = op1 * op2;
                        break;
                    case '/':
                        val = op1 / op2;
                        break;
                }

                push(&operands, val);
            }
            // 弹出'('
            pop(&operators);
        }
        // 如果是操作符，则将其入栈，
        // 并将运算符栈中优先级大于等于当前操作符的运算符取出并计算
        else if (isOperator(ch)) {
            while (!isEmpty(&operators) && peek(&operators) != '('
                   && getPriority(peek(&operators)) >= getPriority(ch)) {
                op2 = pop(&operands);
                op1 = pop(&operands);
                val = pop(&operators);

                switch (val) {
                    case '+':
                        val = op1 + op2;
                        break;
                    case '-':
                        val = op1 - op2;
                        break;
                    case '*':
                        val = op1 * op2;
                        break;
                    case '/':
                        val = op1 / op2;
                        break;
                }

                push(&operands, val);
            }

            // 将当前操作符入栈
            push(&operators, ch);
        }

        prev = ch;
    }

    // 处理所有剩余的操作符
    while (!isEmpty(&operators)) {
        op2 = pop(&operands);
        op1 = pop(&operands);
        val = pop(&operators);

        switch (val) {
            case '+':
                val = op1 + op2;
                break;
            case '-':
                val = op1 - op2;
                break;
            case '*':
                val = op1 * op2;
                break;
            case '/':
                val = op1 / op2;
                break;
        }

        push(&operands, val);
    }

    return pop(&operands);
}

// 测试函数
int main() {
    char expression[100];

    printf("Enter an arithmetic expression: ");
    fgets(expression, 100, stdin);

    printf("Result: %d\n", evaluate(expression));

    return 0;
}

这个代码实现了基本的四则运算和括号优先级，可以处理多位数和负数。不过可能还存在一些漏洞，需要自己进一步完善和测试。

堆栈实现算数表达式

堆栈可以用来实现算数表达式的计算。

具体实现步骤如下：

1. 创建一个操作数栈和一个操作符栈。

2. 从左到右遍历表达式，对于每个字符：

- 如果它是一个数字，则将其压入操作数栈。

- 如果它是一个操作符，则将其压入操作符栈。

- 如果它是一个右括号，则弹出操作符栈中的操作符和操作数栈中的操作数，直到遇到左括号为止。然后将计算结果压入操作数栈。

3. 最后，操作符栈中可能还有操作符，需要按照优先级顺序弹出操作符并计算，直到操作符栈为空。最后的操作数栈中的元素即为表达式的计算结果。

下面是一个示例代码，实现了一个简单的算数表达式计算器：

class Stack:
    def __init__(self):
        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 is_empty(self):
        return len(self.items) == 0

def calculate(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, ')': 0}
    
    operand_stack = Stack()
    operator_stack = Stack()
    
    for token in expression:
        if token.isdigit():
            operand_stack.push(int(token))
        elif token in '+-*/':
            while not operator_stack.is_empty() and precedence[token] <= precedence[operator_stack.peek()]:
                operator = operator_stack.pop()
                operand2 = operand_stack.pop()
                operand1 = operand_stack.pop()
                result = eval(f'{operand1} {operator} {operand2}')
                operand_stack.push(result)
            operator_stack.push(token)
        elif token == '(':
            operator_stack.push(token)
        elif token == ')':
            while operator_stack.peek() != '(':
                operator = operator_stack.pop()
                operand2 = operand_stack.pop()
                operand1 = operand_stack.pop()
                result = eval(f'{operand1} {operator} {operand2}')
                operand_stack.push(result)
            operator_stack.pop()
    
    while not operator_stack.is_empty():
        operator = operator_stack.pop()
        operand2 = operand_stack.pop()
        operand1 = operand_stack.pop()
        result = eval(f'{operand1} {operator} {operand2}')
        operand_stack.push(result)
    
    return operand_stack.pop()

expression = '2 * (3 + 4) - 5 / 2'
result = calculate(expression)
print(f'{expression} = {result}')

输出结果为：

2 * (3 + 4) - 5 / 2 = 13.5

注意，这个实现只支持整数和四则运算，没有处理错误输入和除数为0的情况。在实际应用中，需要加入更多的判断和处理逻辑。