算术表达式的求解 问题描述:给定一个算术表达式,通过c语言程序求出最后的结果。 基本要求: 1. 从键盘输入要求解的算术表达式: 2.采用栈结构进行算术表达式的求解过程;.能够判断算术表达式正确与否: 4.对于错误表达式给出提示; 5.对于正确的表达式给出最后的结果;
时间: 2024-03-19 12:45:45 浏览: 62
好的,这是一个比较常见的算法问题。首先,需要将输入的算术表达式转换成逆波兰表达式,然后再使用栈结构求解逆波兰表达式。下面是一个基本的思路:
1. 从键盘读取算术表达式,可以使用fgets()函数。
2. 创建一个运算符栈和一个结果栈,分别用于存储运算符和中间结果。
3. 遍历表达式中的每个字符,如果是数字则直接入结果栈,如果是运算符则与运算符栈顶元素比较优先级,如果当前运算符优先级低于或等于栈顶运算符则将栈顶运算符出栈并将其压入结果栈,然后将当前运算符入栈。如果当前运算符优先级高于栈顶运算符则直接将其入栈。
4. 遍历完表达式后,将运算符栈中剩余的元素全部出栈并压入结果栈。
5. 检查结果栈中是否只剩下一个元素,如果是则输出该元素,否则说明表达式有误。
下面是一个简单的实现代码,仅供参考:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define STACK_SIZE 100
typedef struct {
int top;
char data[STACK_SIZE];
} Stack;
void push(Stack *s, char c) {
if (s->top == STACK_SIZE - 1) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = c;
}
char pop(Stack *s) {
if (s->top == -1) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
int is_operator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int get_priority(char c) {
if (c == '+' || c == '-') {
return 1;
} else if (c == '*' || c == '/') {
return 2;
} else {
return 0;
}
}
void convert_to_rpn(char *expr, char *rpn) {
Stack op_stack = {-1, {0}};
int i, j;
char c;
for (i = j = 0; expr[i]; i++) {
if (isspace(expr[i])) {
continue;
} else if (isdigit(expr[i])) {
while (isdigit(expr[i])) {
rpn[j++] = expr[i++];
}
rpn[j++] = ' ';
i--;
} else if (is_operator(expr[i])) {
while (op_stack.top != -1 && get_priority(expr[i]) <= get_priority(op_stack.data[op_stack.top])) {
rpn[j++] = pop(&op_stack);
rpn[j++] = ' ';
}
push(&op_stack, expr[i]);
} else if (expr[i] == '(') {
push(&op_stack, expr[i]);
} else if (expr[i] == ')') {
while ((c = pop(&op_stack)) != '(') {
rpn[j++] = c;
rpn[j++] = ' ';
}
} else {
printf("Invalid character: %c\n", expr[i]);
exit(1);
}
}
while (op_stack.top != -1) {
if (!is_operator(op_stack.data[op_stack.top])) {
printf("Invalid expression\n");
exit(1);
}
rpn[j++] = pop(&op_stack);
rpn[j++] = ' ';
}
rpn[j] = '\0';
}
int evaluate_rpn(char *rpn) {
Stack result_stack = {-1, {0}};
int i, a, b, result;
char *token;
for (i = 0; rpn[i]; i++) {
if (isspace(rpn[i])) {
continue;
} else if (isdigit(rpn[i])) {
result = 0;
while (isdigit(rpn[i])) {
result = result * 10 + rpn[i++] - '0';
}
push(&result_stack, result);
i--;
} else if (is_operator(rpn[i])) {
b = pop(&result_stack);
a = pop(&result_stack);
switch (rpn[i]) {
case '+': push(&result_stack, a + b); break;
case '-': push(&result_stack, a - b); break;
case '*': push(&result_stack, a * b); break;
case '/': push(&result_stack, a / b); break;
}
} else {
printf("Invalid character: %c\n", rpn[i]);
exit(1);
}
}
result = pop(&result_stack);
if (result_stack.top != -1) {
printf("Invalid expression\n");
exit(1);
}
return result;
}
int main() {
char expr[100], rpn[100];
printf("Enter an arithmetic expression: ");
fgets(expr, sizeof(expr), stdin);
convert_to_rpn(expr, rpn);
printf("RPN: %s\n", rpn);
printf("Result: %d\n", evaluate_rpn(rpn));
return 0;
}
```
阅读全文