使用栈实现表达式求值的一般方法如下:
1.定义两个栈,一个用于存储操作数,另一个用于存储操作符。
2.遍历表达式中的每个字符,按照以下规则处理:
如果字符是操作数,则将其转换为整数,并将其压入操作数栈中。
如果字符是操作符,则按照以下步骤处理:
3.遍历完整个表达式后,检查操作符栈是否为空,如果不为空,则从操作数栈中弹出两个操作数, 从操作符栈中弹出一个操作符,进行计算并将结果压入操作数栈中,直到操作符栈为空。
4.最后,操作数栈中剩下的唯一一个元素就是表达式的最终结果。
以下是一个使用栈实现表达式求值的示例代码:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 100
// 定义栈结构
typedef struct {
int data[MAX_SIZE];
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 == MAX_SIZE - 1;
}
// 元素入栈
void push(Stack* s, int val) {
if (isFull(s)) {
printf("Stack is full!\n");
return;
}
s->data[++s->top] = val;
}
// 元素出栈
int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return -1;
}
return s->data[s->top--];
}
// 获取栈顶元素
int top(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return -1;
}
return s->data[s->top];
}
// 获取操作符的优先级
int getPriority(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
// 执行计算
int calculate(int num1, int num2, char op) {
switch (op) {
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
case '/':
return num1 / num2;
default:
return 0;
}
}
// 使用栈求解表达式的值
int evaluateExpression(char* expression) {
Stack numStack; // 操作数栈
Stack opStack; // 操作符栈
initStack(&numStack);
initStack(&opStack);
int num = 0; // 用于处理多位数
int sign = 1; // 用于处理负数