用C语言实现实现栈的应用表达式求值 采用顺序栈实现表达式求值 从运行界面输入一个表达式 该表达式包括加法 减法 乘法 除法
时间: 2024-02-19 16:04:01 浏览: 76
好的,我理解了你的问题。下面是用C语言实现栈的应用表达式求值的代码,采用顺序栈实现表达式求值的思路:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义栈的结构体
typedef struct {
int* data;
int top; // 栈顶指针
int size; // 栈的大小
} Stack;
// 初始化栈
void initStack(Stack* s, int size) {
s->data = (int*)malloc(sizeof(int) * size);
s->top = -1;
s->size = size;
}
// 判断栈是否为空
int isEmpty(Stack* s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(Stack* s) {
return s->top == s->size - 1;
}
// 入栈
void push(Stack* s, int x) {
if (isFull(s)) {
printf("Stack is Full!\n");
return;
}
s->data[++s->top] = x;
}
// 出栈
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 isDigit(char c) {
return c >= '0' && c <= '9';
}
// 判断是否为运算符
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
// 获取运算符的优先级
int getPriority(char c) {
if (c == '+' || c == '-')
return 1;
if (c == '*' || c == '/')
return 2;
return 0;
}
// 计算表达式的值
int calculate(char op, int a, int b) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
return 0;
}
// 表达式求值的函数
int evaluate(char* expr) {
int i, num = 0;
Stack nums, ops;
initStack(&nums, strlen(expr));
initStack(&ops, strlen(expr));
for (i = 0; expr[i] != '\0'; i++) {
if (isDigit(expr[i])) {
num = num * 10 + (expr[i] - '0');
if (!isDigit(expr[i+1])) {
push(&nums, num);
num = 0;
}
} else if (isOperator(expr[i])) {
while (!isEmpty(&ops) && getPriority(top(&ops)) >= getPriority(expr[i])) {
int b = pop(&nums);
int a = pop(&nums);
char op = pop(&ops);
push(&nums, calculate(op, a, b));
}
push(&ops, expr[i]);
}
}
while (!isEmpty(&ops)) {
int b = pop(&nums);
int a = pop(&nums);
char op = pop(&ops);
push(&nums, calculate(op, a, b));
}
return pop(&nums);
}
// 主函数
int main() {
char expr[100];
printf("Please input an expression: ");
scanf("%s", expr);
printf("Result: %d\n", evaluate(expr));
return 0;
}
```
这个程序会提示用户输入一个表达式,然后使用栈的思路计算出表达式的值并输出。注意,这个程序只支持整数的加、减、乘、除四种运算符,不支持括号等复杂的运算符和表达式。
阅读全文