用栈简单实现表达式求值

以下是使用栈简单实现表达式求值的Python代码：

def calculate(expression):
    stack = []
    for char in expression:
        if char.isdigit():
            stack.append(int(char))
        else:
            num2 = stack.pop()
            num1 = stack.pop()
            if char == "+":
                stack.append(num1 + num2)
            elif char == "-":
                stack.append(num1 - num2)
            elif char == "*":
                stack.append(num1 * num2)
            elif char == "/":
                stack.append(num1 / num2)
    return stack.pop()

该函数接受一个字符串类型的表达式作为参数，然后遍历表达式字符，如果字符是数字，则将其转换为整数并压入栈中。如果字符是运算符，则弹出栈顶的两个数字进行相应的运算，然后将结果压入栈中。最后，栈中只剩下一个数字，即为表达式的求值结果。

相关问题

用栈实现简单表达式求值

算法思路：

- 遍历表达式中的每一个字符：
- 如果字符是数字，将其转化为数字后入栈。
- 如果字符是运算符，弹出栈顶的两个数字进行计算，计算结果入栈。
- 遍历结束后，栈内剩下的唯一元素即为表达式的计算结果。

代码实现：

import java.util.Stack;

public class ExpressionEvaluation {
    public int evaluate(String expression) {
        Stack<Integer> operandStack = new Stack<>();
        Stack<Character> operatorStack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (Character.isDigit(c)) {
                operandStack.push(Character.getNumericValue(c));
            } else if (c == '+' || c == '-') {
                while (!operatorStack.isEmpty() && (operatorStack.peek() == '+' || operatorStack.peek() == '-')) {
                    char operator = operatorStack.pop();
                    int operand2 = operandStack.pop();
                    int operand1 = operandStack.pop();
                    int result = applyOperation(operator, operand1, operand2);
                    operandStack.push(result);
                }
                operatorStack.push(c);
            } else if (c == '*' || c == '/') {
                while (!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    char operator = operatorStack.pop();
                    int operand2 = operandStack.pop();
                    int operand1 = operandStack.pop();
                    int result = applyOperation(operator, operand1, operand2);
                    operandStack.push(result);
                }
                operatorStack.push(c);
            }
        }
        while (!operatorStack.isEmpty()) {
            char operator = operatorStack.pop();
            int operand2 = operandStack.pop();
            int operand1 = operandStack.pop();
            int result = applyOperation(operator, operand1, operand2);
            operandStack.push(result);
        }
        return operandStack.pop();
    }

    private int applyOperation(char operator, int operand1, int operand2) {
        if (operator == '+') {
            return operand1 + operand2;
        } else if (operator == '-') {
            return operand1 - operand2;
        } else if (operator == '*') {
            return operand1 * operand2;
        } else if (operator == '/') {
            return operand1 / operand2;
        } else {
            throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }
}

使用样例：

ExpressionEvaluation expressionEvaluation = new ExpressionEvaluation();
int result = expressionEvaluation.evaluate("2 + 3 * 4 - 5");
System.out.println(result); // Output: 9

用C语言栈实现简单表达式求值

以下是使用C语言栈实现简单表达式求值的示例代码：

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

// 定义栈结构
typedef struct Stack {
    int *array;
    int top;
    int capacity;
} Stack;

// 初始化栈
Stack* createStack(int capacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->array = (int*)malloc(sizeof(int) * capacity);
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

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

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

// 入栈
void push(Stack *stack, int value) {
    if (isFull(stack)) {
        printf("Stack is full\n");
        return;
    }
    stack->top++;
    stack->array[stack->top] = value;
}

// 出栈
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    int value = stack->array[stack->top];
    stack->top--;
    return value;
}

// 获取栈顶元素
int peek(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->array[stack->top];
}

// 计算表达式
int calculate(int num1, char op, int num2) {
    int result = 0;
    switch (op) {
        case '+': result = num1 + num2; break;
        case '-': result = num1 - num2; break;
        case '*': result = num1 * num2; break;
        case '/': result = num1 / num2; break;
    }
    return result;
}

// 求值
int evaluate(char *expression) {
    Stack *stack = createStack(50);
    int i, num1, num2, result;
    char op;
    for (i = 0; expression[i] != '\0'; i++) {
        // 如果是数字字符，入栈
        if (expression[i] >= '0' && expression[i] <= '9') {
            push(stack, expression[i] - '0');
        }
        // 如果是操作符，弹出两个数字，计算结果，再入栈
        else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/') {
            num2 = pop(stack);
            num1 = pop(stack);
            result = calculate(num1, expression[i], num2);
            push(stack, result);
        }
    }
    // 最后栈内只剩一个元素即为结果
    result = pop(stack);
    free(stack->array);
    free(stack);
    return result;
}

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

示例输入：

Enter an expression: 25+3*6-8/2

示例输出：

Result: 35