c语言堆栈表达式求值

C语言中的堆栈可以用来实现表达式求值。具体实现方法如下：

1. 定义两个栈，一个操作数栈，一个操作符栈；
2. 从左到右扫描表达式，遇到操作数则压入操作数栈，遇到操作符则与操作符栈栈顶的操作符进行比较，如果优先级低于或等于栈顶操作符，则弹出栈顶操作符和两个操作数进行运算，并将结果压入操作数栈；否则将该操作符压入操作符栈；
3. 扫描完毕后，将操作符栈中的操作符全部弹出并与相应的操作数进行运算，并将结果压入操作数栈，直到操作符栈为空；
4. 操作数栈中剩下的唯一元素即为表达式的值。

相关问题

c语言堆栈表达式求值的代码

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

#define MAXSIZE 100 // 定义堆栈最大容量

// 定义堆栈结构体
typedef struct {
int data[MAXSIZE];
int top;
} Stack;

// 初始化堆栈
void initStack(Stack *s) {
s->top = -1;
}

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

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

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

// 出栈
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top--];
}

// 取栈顶元素
int getTop(Stack *s) {
if (isEmpty(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;
case '(':
return 0;
default:
printf("Invalid operator.\n");
exit(1);
}
}

// 计算表达式的值
int calc(int a, int b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
if (b == 0) {
printf("Divide by zero.\n");
exit(1);
}
return a / b;
default:
printf("Invalid operator.\n");
exit(1);
}
}

// 中缀表达式求值
int evaluate(char *exp) {
Stack opnd, optr; // 定义操作数堆栈和操作符堆栈
initStack(&opnd);
initStack(&optr);
push(&optr, '('); // 在操作符堆栈底部压入'('
char *p = exp;
while (*p != '\0') {
if (*p >= '0' && *p <= '9') { // 如果是操作数，直接入操作数堆栈
int num = 0;
while (*p >= '0' && *p <= '9') {
num = num * 10 + *p - '0';
p++;
}
push(&opnd, num);
} else if (*p == '(') { // 如果是左括号，直接入操作符堆栈
push(&optr, '(');
p++;
} else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') { // 如果是操作符
while (priority(getTop(&optr)) >= priority(*p)) { // 循环弹出操作符堆栈中优先级不小于当前操作符的操作符，并将其与操作数堆栈中两个操作数进行计算，将结果入操作数堆栈
char op = pop(&optr);
int b = pop(&opnd);
int a = pop(&opnd);
int res = calc(a, b, op);
push(&opnd, res);
}
push(&optr, *p); // 当前操作符入操作符堆栈
p++;
} else if (*p == ')') { // 如果是右括号
while (getTop(&optr) != '(') { // 循环弹出操作符堆栈中左括号之后的操作符，并将其与操作数堆栈中两个操作数进行计算，将结果入操作数堆栈
char op = pop(&optr);
int b = pop(&opnd);
int a = pop(&opnd);
int res = calc(a, b, op);
push(&opnd, res);
}
pop(&optr); // 弹出左括号
p++;
} else {
printf("Invalid character.\n");
exit(1);
}
}
while (!isEmpty(&optr)) { // 处理操作符堆栈中剩余的操作符
char op = pop(&optr);
int b = pop(&opnd);
int a = pop(&opnd);
int res = calc(a, b, op);
push(&opnd, res);
}
return pop(&opnd); // 返回操作数堆栈中的唯一元素，即表达式的值
}

int main() {
char exp[MAXSIZE];
printf("Please input an infix expression:\n");
scanf("%s", exp);
int res = evaluate(exp);
printf("The result is: %d\n", res);
return 0;
}

c语言堆栈后缀表达式求值

好的，针对您的问题，我可以给出以下步骤：

1. 创建一个栈，用于存储操作数和运算符。
2. 从左到右扫描后缀表达式，如果是操作数，则将其压入栈中。
3. 如果是运算符，则从栈中弹出两个操作数进行计算，并将结果压入栈中。
4. 最终栈中只剩下一个元素，即为表达式的值。

以下是一个示例代码实现：

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

#define MAX_STACK_SIZE 100

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

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

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

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

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

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

int evaluatePostfix(char *expr) {
    Stack s;
    initStack(&s);

    for (int i = 0; expr[i] != '\0'; i++) {
        if (isdigit(expr[i])) {
            push(&s, expr[i] - '0');
        } else {
            int op2 = pop(&s);
            int op1 = pop(&s);
            switch (expr[i]) {
                case '+':
                    push(&s, op1 + op2);
                    break;
                case '-':
                    push(&s, op1 - op2);
                    break;
                case '*':
                    push(&s, op1 * op2);
                    break;
                case '/':
                    push(&s, op1 / op2);
                    break;
                default:
                    printf("Invalid operator\n");
                    exit(1);
            }
        }
    }

    if (isEmpty(&s)) {
        printf("Expression is empty\n");
        exit(1);
    }

    int result = pop(&s);

    if (!isEmpty(&s)) {
        printf("Invalid expression\n");
        exit(1);
    }

    return result;
}

int main() {
    char expr[] = "23+4*";
    int result = evaluatePostfix(expr);
    printf("Result: %d\n", result);

    return 0;
}