用户从键盘输入一个算术表达式,数字都是十进制整型(必须支持负数),运算符支持+-*/()。编写源程序中的 double deal_exp (char *exp) 函数,对这个算术表达式求值,返回结果。
时间: 2024-02-06 14:11:19 浏览: 85
好的,我来解答您的问题。
首先,您需要将中缀表达式转换为后缀表达式。这可以通过使用栈来实现。具体步骤如下:
1. 创建一个运算符栈和一个结果栈。
2. 从左到右遍历表达式中的每个字符。
3. 如果字符是数字,则将它压入结果栈。
4. 如果字符是左括号,则将其压入运算符栈。
5. 如果字符是右括号,则将运算符栈中的运算符弹出并压入结果栈,直到遇到左括号为止。
6. 如果字符是运算符,则将其压入运算符栈。但在压入之前,需要先将运算符栈中优先级大于或等于该运算符的运算符弹出并压入结果栈。
7. 最后,将运算符栈中剩余的运算符依次弹出并压入结果栈。
完成后,您会得到一个后缀表达式。接下来,您可以使用另一个栈来计算后缀表达式的值。具体步骤如下:
1. 创建一个栈。
2. 从左到右遍历后缀表达式中的每个字符。
3. 如果字符是数字,则将其压入栈。
4. 如果字符是运算符,则从栈中弹出两个操作数,并根据运算符进行计算。将计算结果压入栈。
5. 最后,栈中只剩下一个元素,即为最终结果。
下面是示例代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
typedef struct _stack {
int top;
int capacity;
double *data;
} Stack;
Stack* create_stack(int capacity) {
Stack *stack = malloc(sizeof(Stack));
stack->top = -1;
stack->capacity = capacity;
stack->data = malloc(sizeof(double) * capacity);
return stack;
}
void push(Stack *stack, double value) {
if (stack->top == stack->capacity - 1) {
printf("Stack overflow!\n");
return;
}
stack->top++;
stack->data[stack->top] = value;
}
double pop(Stack *stack) {
if (stack->top == -1) {
printf("Stack underflow!\n");
return 0.0;
}
double value = stack->data[stack->top];
stack->top--;
return value;
}
double peek(Stack *stack) {
if (stack->top == -1) {
printf("Stack underflow!\n");
return 0.0;
}
return stack->data[stack->top];
}
int is_empty(Stack *stack) {
return stack->top == -1;
}
int is_operator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int precedence(char c) {
if (c == '*' || c == '/') {
return 2;
} else if (c == '+' || c == '-') {
return 1;
} else {
return 0;
}
}
double evaluate(char *exp) {
Stack *operator_stack = create_stack(strlen(exp));
Stack *result_stack = create_stack(strlen(exp));
int i = 0;
while (exp[i] != '\0') {
if (isdigit(exp[i]) || (exp[i] == '-' && i == 0)) {
char *endptr;
double value = strtod(&exp[i], &endptr);
push(result_stack, value);
i = endptr - exp;
} else if (exp[i] == '(') {
push(operator_stack, exp[i]);
i++;
} else if (exp[i] == ')') {
while (!is_empty(operator_stack) && peek(operator_stack) != '(') {
char op = pop(operator_stack);
double operand2 = pop(result_stack);
double operand1 = pop(result_stack);
double result;
switch (op) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
push(result_stack, result);
}
pop(operator_stack);
i++;
} else if (is_operator(exp[i])) {
while (!is_empty(operator_stack) && precedence(peek(operator_stack)) >= precedence(exp[i])) {
char op = pop(operator_stack);
double operand2 = pop(result_stack);
double operand1 = pop(result_stack);
double result;
switch (op) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
push(result_stack, result);
}
push(operator_stack, exp[i]);
i++;
} else {
printf("Invalid character: %c\n", exp[i]);
return 0.0;
}
}
while (!is_empty(operator_stack)) {
char op = pop(operator_stack);
double operand2 = pop(result_stack);
double operand1 = pop(result_stack);
double result;
switch (op) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
push(result_stack, result);
}
double result = pop(result_stack);
free(operator_stack->data);
free(operator_stack);
free(result_stack->data);
free(result_stack);
return result;
}
int main() {
char exp[100];
printf("Enter an arithmetic expression: ");
fgets(exp, 100, stdin);
printf("Result: %.2f\n", evaluate(exp));
return 0;
}
```
在这个示例代码中,我们使用了两个栈来实现中缀表达式到后缀表达式的转换和后缀表达式的计算。其中,is_empty()、peek()、push()、pop() 函数实现了栈的基本操作。evaluate() 函数是主函数,它接受一个中缀表达式作为参数,并返回计算结果。
在该函数中,我们首先创建了一个运算符栈和一个结果栈。然后,我们从左到右遍历中缀表达式中的每个字符,并根据字符的类型进行不同的操作。最后,我们计算结果栈中的结果并返回计算结果。
这就是一个简单的中缀表达式求值程序。希望对您有所帮助。
阅读全文