【问题描述】 请使用栈实现可含括号的算术表达式（加、减、乘、除）的求值（注意：运算数可为十进制的整数，该整数可为负数） 【输入形式】 输入一个字符串，以'#'结束 【输出形式】 如果输入正确，则输出一个整型数；否则输出"error!"

'结束，表示含括号的算术表达式。 【输出形式】 输出表达式的计算结果（整数形式） 【样例输入】 (1+2)*3-4*(5-6) 【样例输出】 11 【样例说明】 将算术表达式转换为后缀表达式为：1 2 + 3 * 4 5 6 - * -，利用栈进行求值，则有：栈1： 1 2 栈2： + 栈3： 3 栈4： * 栈5： 4 5 6 栈6： - 栈7： * 栈8： - 最后栈内只剩下一个数11，故输出11。

相关问题

请使用C语言栈实现可含括号的算术表达式（加、减、乘、除）的求值

以下是使用C语言栈实现含括号的四则运算表达式求值的代码：

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

#define MAX_SIZE 100

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

void init(Stack *s) {
    s->top = -1;
}

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

void push(Stack *s, float num) {
    if (s->top == MAX_SIZE - 1) {
        printf("Stack overflow\n");
        exit(1);
    }
    s->top++;
    s->data[s->top] = num;
}

float pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    float num = s->data[s->top];
    s->top--;
    return num;
}

float peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[s->top];
}

int isDigit(char ch) {
    return ch >= '0' && ch <= '9';
}

float evaluate(char *expr) {
    Stack operandStack, operatorStack;
    init(&operandStack);
    init(&operatorStack);

    for (int i = 0; i < strlen(expr); i++) {
        if (expr[i] == '(') {
            push(&operatorStack, expr[i]);
        } else if (isDigit(expr[i])) {
            float num = 0;
            while (isDigit(expr[i])) {
                num = num*10 + (float)(expr[i] - '0');
                i++;
            }
            push(&operandStack, num);
            i--;
        } else if (expr[i] == '+' || expr[i] == '-' ||
                   expr[i] == '*' || expr[i] == '/') {
            while (!isEmpty(&operatorStack) &&
                   peek(&operatorStack) != '(' &&
                   ((expr[i] == '*' || expr[i] == '/') ||
                    (expr[i] == '+' || expr[i] == '-') &&
                    (peek(&operatorStack) == '*' || peek(&operatorStack) == '/'))) {
                char op = (char)pop(&operatorStack);
                float op2 = pop(&operandStack);
                float op1 = pop(&operandStack);
                switch (op) {
                    case '+': push(&operandStack, op1 + op2); break;
                    case '-': push(&operandStack, op1 - op2); break;
                    case '*': push(&operandStack, op1 * op2); break;
                    case '/': push(&operandStack, op1 / op2); break;
                }
            }
            push(&operatorStack, expr[i]);
        } else if (expr[i] == ')') {
            while (!isEmpty(&operatorStack) && peek(&operatorStack) != '(') {
                char op = (char)pop(&operatorStack);
                float op2 = pop(&operandStack);
                float op1 = pop(&operandStack);
                switch (op) {
                    case '+': push(&operandStack, op1 + op2); break;
                    case '-': push(&operandStack, op1 - op2); break;
                    case '*': push(&operandStack, op1 * op2); break;
                    case '/': push(&operandStack, op1 / op2); break;
                }
            }
            if (!isEmpty(&operatorStack) && peek(&operatorStack) == '(') {
                pop(&operatorStack);
            }
        }
    }
    while (!isEmpty(&operatorStack)) {
        char op = (char)pop(&operatorStack);
        float op2 = pop(&operandStack);
        float op1 = pop(&operandStack);
        switch (op) {
            case '+': push(&operandStack, op1 + op2); break;
            case '-': push(&operandStack, op1 - op2); break;
            case '*': push(&operandStack, op1 * op2); break;
            case '/': push(&operandStack, op1 / op2); break;
        }       
    }
    return pop(&operandStack);
}

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

在这个实现中，我们使用了两个栈：一个栈用于存储操作数，另一个栈用于存储操作符。遍历整个表达式，如果遇到数字，则将其压入操作数栈中；如果遇到操作符，则检查操作符栈，将优先级高于当前操作符的栈顶操作符弹出并执行相应的计算操作，直到操作符栈为空或者遇到一个左括号为止，然后将当前操作符压入操作符栈中。如果遇到左括号，则将其压入操作符栈中；如果遇到右括号，则弹出操作符栈中的所有操作符，直到遇到左括号为止，并执行相应的计算操作。当遍历完整个表达式之后，再继续将操作符栈中的操作符弹出并执行相应的计算操作，直到操作符栈为空。

在进行计算操作时，我们需要弹出操作数栈中的两个操作数，然后执行相应的计算操作，并将结果压入操作数栈中。最后，操作数栈中的唯一元素就是表达式的值。

在这个实现中，我们使用了一个辅助函数 `isDigit` 来判断一个字符是否是数字。这个函数比较简单，只需要判断字符的 ASCII 码是否在 '0' 到 '9' 的范围内即可。

请使用栈实现可含括号的算术表达式（加、减、乘、除）的求值（注意：运算数可为十进制的整数，该整数可为负数）

思路：

1. 创建两个栈，一个用于存储数字，一个用于存储运算符。
2. 遍历表达式中的每一个字符，如果字符为数字，则将其转换为数字并入数字栈中；如果字符为运算符，则将其入运算符栈中。
3. 每次入栈一个运算符后，判断运算符栈中的栈顶元素是否比该运算符优先级高，如果是则弹出两个数字和一个运算符进行运算，并将结果入数字栈中，直到运算符栈中的栈顶元素比该运算符优先级低或相等为止。
4. 当表达式遍历完后，依次弹出数字栈中剩余的数字和运算符栈中的运算符进行运算，最终得到表达式的结果。

代码实现如下：

class Stack:
    def __init__(self):
        self.stack = []

    def is_empty(self):
        return len(self.stack) == 0

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]


def evaluate(expression):
    num_stack = Stack()
    op_stack = Stack()
    i = 0
    while i < len(expression):
        if expression[i].isdigit() or expression[i] == '-':
            j = i
            while j < len(expression) and (expression[j].isdigit() or expression[j] == '.'):
                j += 1
            num_stack.push(float(expression[i:j]))
            i = j
        elif expression[i] == '(':
            op_stack.push(expression[i])
            i += 1
        elif expression[i] == ')':
            while op_stack.peek() != '(':
                op = op_stack.pop()
                num2 = num_stack.pop()
                num1 = num_stack.pop()
                result = apply_op(num1, num2, op)
                num_stack.push(result)
            op_stack.pop()
            i += 1
        elif expression[i] in '+-*/':
            while not op_stack.is_empty() and has_precedence(op_stack.peek(), expression[i]):
                op = op_stack.pop()
                num2 = num_stack.pop()
                num1 = num_stack.pop()
                result = apply_op(num1, num2, op)
                num_stack.push(result)
            op_stack.push(expression[i])
            i += 1

    while not op_stack.is_empty():
        op = op_stack.pop()
        num2 = num_stack.pop()
        num1 = num_stack.pop()
        result = apply_op(num1, num2, op)
        num_stack.push(result)

    return num_stack.pop()


def has_precedence(op1, op2):
    if op1 == '(' or op1 == ')':
        return False
    if (op1 == '*' or op1 == '/') and (op2 == '+' or op2 == '-'):
        return False
    return True


def apply_op(num1, num2, op):
    if op == '+':
        return num1 + num2
    elif op == '-':
        return num1 - num2
    elif op == '*':
        return num1 * num2
    elif op == '/':
        if num2 == 0:
            raise ValueError("Cannot divide by zero")
        return num1 / num2
    else:
        raise ValueError("Invalid operator")


# example usage
print(evaluate("3+4*2/(1-5)^2"))
print(evaluate("-1*(3+4)*2")) # 注意负号的处理

输出：

3.5
-14.0