用c语言实现:从键盘输入一个算数表达式,完成表达式求值,要求: 1、实现栈,并用栈完成; 2、表达式中数字可以为一位数; 3、表达式中的符号包括:加、减、乘、除、小括号,注意小括号的运算优先于其他符号
时间: 2023-07-10 10:07:16 浏览: 52
以下是使用C语言实现的算法,通过栈实现表达式求值:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义栈结构体
typedef struct {
int top;
int *data;
} Stack;
// 初始化栈
void initStack(Stack *s, int size) {
s->data = (int *) malloc(size * sizeof(int));
s->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}
// 入栈操作
void push(Stack *s, int value) {
s->top++;
s->data[s->top] = value;
}
// 出栈操作
int pop(Stack *s) {
int value = s->data[s->top];
s->top--;
return value;
}
// 获取栈顶元素
int peek(Stack *s) {
return s->data[s->top];
}
// 判断是否为运算符
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
// 获取运算符优先级
int getPriority(char c) {
if (c == '*' || c == '/') {
return 2;
} else if (c == '+' || c == '-') {
return 1;
} else {
return 0;
}
}
// 计算表达式
int calculate(int a, int b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
default:
return 0;
}
}
// 表达式求值
int evaluateExpression(char *expression) {
Stack numStack, opStack;
initStack(&numStack, 100);
initStack(&opStack, 100);
int i = 0;
while (expression[i] != '\0') {
if (expression[i] == ' ') {
i++;
continue;
}
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) != '(') {
char op = pop(&opStack);
int b = pop(&numStack);
int a = pop(&numStack);
int result = calculate(a, b, op);
push(&numStack, result);
}
pop(&opStack);
i++;
} else if (isOperator(expression[i])) {
while (!isEmpty(&opStack) && getPriority(expression[i]) <= getPriority(peek(&opStack))) {
char op = pop(&opStack);
int b = pop(&numStack);
int a = pop(&numStack);
int result = calculate(a, b, op);
push(&numStack, result);
}
push(&opStack, expression[i]);
i++;
} else {
i++;
}
}
while (!isEmpty(&opStack)) {
char op = pop(&opStack);
int b = pop(&numStack);
int a = pop(&numStack);
int result = calculate(a, b, op);
push(&numStack, result);
}
int result = pop(&numStack);
free(numStack.data);
free(opStack.data);
return result;
}
int main() {
char expression[100];
printf("请输入算数表达式:\n");
scanf("%[^\n]", expression);
int result = evaluateExpression(expression);
printf("表达式的结果为:%d\n", result);
return 0;
}
```
使用方法:
1. 编译代码:`gcc expression.c -o expression`
2. 运行程序:`./expression`
3. 输入算数表达式,例如:`(1+2)*3-4/2`
4. 程序将输出表达式的结果
注意事项:
1. 程序中使用了两个栈,一个存储数字,一个存储运算符
2. 程序中使用了逆波兰表达式求值的思路,具体实现可以参考代码
3. 程序中没有对输入表达式的合法性进行检查,如果表达式不合法可能会出现错误