利用堆栈计算表达式c语言

可以使用堆栈来计算中缀表达式，具体步骤如下：

1. 定义一个操作数栈和一个操作符栈。
2. 从左到右扫描表达式，如果遇到操作数，则压入操作数栈。
3. 如果遇到操作符，将其与操作符栈栈顶元素进行比较：
- 如果操作符栈为空，或者栈顶操作符为左括号，则直接将此操作符入栈。
- 否则，若优先级比栈顶操作符优先级高，则将此操作符入栈。
- 否则，将操作符栈栈顶元素弹出并压入操作数栈中，再次转到3.1与新的栈顶操作符比较。
4. 如果遇到左括号，则直接压入操作符栈。
5. 如果遇到右括号，则执行出栈操作，直到遇到左括号为止，将这一对括号丢弃。
6. 重复步骤2至5，直到表达式的最右边。
7. 最后将操作符栈中剩余的操作符依次弹出并压入操作数栈中。
8. 操作数栈顶元素即为表达式的结果。

下面是一个使用堆栈计算表达式的C语言代码示例：

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

typedef struct stack {
    int top;
    int* data;
} Stack;

Stack* createStack(int size) {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    s->top = -1;
    s->data = (int*)malloc(size * sizeof(int));
    return s;
}

void push(Stack* s, int value) {
    s->data[++s->top] = value;
}

int pop(Stack* s) {
    return s->data[s->top--];
}

int peek(Stack* s) {
    return s->data[s->top];
}

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

int priority(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else {
        return 0;
    }
}

int evaluate(char* expression) {
    Stack* numStack = createStack(100);
    Stack* opStack = createStack(100);
    int i = 0;
    while (expression[i] != '\0') {
        if (isdigit(expression[i])) {
            int num = 0;
            while (isdigit(expression[i])) {
                num = num * 10 + (expression[i] - '0');
                i++;
            }
            push(numStack, num);
        } else if (expression[i] == '(') {
            push(opStack, expression[i]);
            i++;
        } else if (expression[i] == ')') {
            while (peek(opStack) != '(') {
                int num2 = pop(numStack);
                int num1 = pop(numStack);
                char op = pop(opStack);
                if (op == '+') {
                    push(numStack, num1 + num2);
                } else if (op == '-') {
                    push(numStack, num1 - num2);
                } else if (op == '*') {
                    push(numStack, num1 * num2);
                } else if (op == '/') {
                    push(numStack, num1 / num2);
                }
            }
            pop(opStack);
            i++;
        } else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/') {
            while (!isEmpty(opStack) && priority(peek(opStack)) >= priority(expression[i])) {
                int num2 = pop(numStack);
                int num1 = pop(numStack);
                char op = pop(opStack);
                if (op == '+') {
                    push(numStack, num1 + num2);
                } else if (op == '-') {
                    push(numStack, num1 - num2);
                } else if (op == '*') {
                    push(numStack, num1 * num2);
                } else if (op == '/') {
                    push(numStack, num1 / num2);
                }
            }
            push(opStack, expression[i]);
            i++;
        } else {
            i++;
        }
    }
    while (!isEmpty(opStack)) {
        int num2 = pop(numStack);
        int num1 = pop(numStack);
        char op = pop(opStack);
        if (op == '+') {
            push(numStack, num1 + num2);
        } else if (op == '-') {
            push(numStack, num1 - num2);
        } else if (op == '*') {
            push(numStack, num1 * num2);
        } else if (op == '/') {
            push(numStack, num1 / num2);
        }
    }
    int result = pop(numStack);
    free(numStack->data);
    free(numStack);
    free(opStack->data);
    free(opStack);
    return result;
}

int main() {
    char expression[] = "1+2*3-(4+5)/6";
    printf("%s = %d\n", expression, evaluate(expression));
    return 0;
}