C语言源代码实现设计一个程序,用算符优先法对算术表达式求值。 三、基本要求: 以字符序列的形式从终端输入语法正确的、不含变量的算术表达式,利用算符优先关系,实现对算术四则混合运算表达式求值。
时间: 2024-05-13 12:17:22 浏览: 179
数据结构课程设计——算术表达式求值
4星 · 用户满意度95%
以下是C语言源代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 100 // 定义栈的大小
// 定义运算符栈
char op_stack[STACK_SIZE];
int op_top = -1;
// 定义操作数栈
int num_stack[STACK_SIZE];
int num_top = -1;
// 获取栈顶元素
char get_op_top() {
if (op_top == -1) {
return '\0';
}
return op_stack[op_top];
}
int get_num_top() {
if (num_top == -1) {
return 0;
}
return num_stack[num_top];
}
// 将字符转换为数字
int char_to_num(char c) {
return c - '0';
}
// 获取运算符优先级
int get_priority(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
// 执行运算
int do_operation(char op, int x, int y) {
switch (op) {
case '+':
return x + y;
case '-':
return x - y;
case '*':
return x * y;
case '/':
if (y == 0) {
printf("Error: divide by zero.\n");
exit(1);
}
return x / y;
default:
return 0;
}
}
// 将数字入栈
void push_num(int num) {
if (num_top == STACK_SIZE - 1) {
printf("Error: num stack overflow.\n");
exit(1);
}
num_stack[++num_top] = num;
}
// 将运算符入栈
void push_op(char op) {
if (op_top == STACK_SIZE - 1) {
printf("Error: op stack overflow.\n");
exit(1);
}
op_stack[++op_top] = op;
}
// 从数字栈中出栈一个元素
int pop_num() {
if (num_top == -1) {
printf("Error: num stack underflow.\n");
exit(1);
}
return num_stack[num_top--];
}
// 从运算符栈中出栈一个元素
char pop_op() {
if (op_top == -1) {
printf("Error: op stack underflow.\n");
exit(1);
}
return op_stack[op_top--];
}
// 计算表达式的值
int evaluate_expression(char* expr) {
int i = 0;
char c = '\0';
int num = 0;
while ((c = expr[i++]) != '\0') {
if (c >= '0' && c <= '9') {
num = char_to_num(c);
// 处理多位数字
while ((c = expr[i]) >= '0' && c <= '9') {
num = num * 10 + char_to_num(c);
i++;
}
push_num(num);
}
else if (c == '(') {
push_op(c);
}
else if (c == ')') {
while (get_op_top() != '(') {
char op = pop_op();
int y = pop_num();
int x = pop_num();
push_num(do_operation(op, x, y));
}
// 弹出左括号
pop_op();
}
else if (c == '+' || c == '-' || c == '*' || c == '/') {
while (get_priority(c) <= get_priority(get_op_top())) {
char op = pop_op();
int y = pop_num();
int x = pop_num();
push_num(do_operation(op, x, y));
}
push_op(c);
}
else {
printf("Error: invalid character in expression.\n");
exit(1);
}
}
while (op_top != -1) {
char op = pop_op();
int y = pop_num();
int x = pop_num();
push_num(do_operation(op, x, y));
}
return get_num_top();
}
int main() {
char expr[STACK_SIZE];
printf("Please input an arithmetic expression:\n");
scanf("%s", expr);
int result = evaluate_expression(expr);
printf("Result: %d\n", result);
return 0;
}
```
使用算符优先法对表达式求值的基本思路是,通过两个栈来处理表达式中的运算符和操作数。当遇到一个数字时,将其入操作数栈;当遇到一个运算符时,与运算符栈中的栈顶元素比较优先级,如果该运算符优先级高于栈顶元素,则将其入栈;否则将运算符栈中栈顶元素弹出,再从操作数栈中弹出两个元素进行计算,并将结果入栈,直到该运算符可以入栈。当遇到一个左括号时,直接将其入运算符栈;当遇到一个右括号时,不断弹出运算符栈中的元素,直到遇到一个左括号为止,将弹出的运算符和操作数进行计算,并将结果入栈。最后,当表达式处理完毕后,将运算符栈中的元素依次弹出,并从操作数栈中弹出两个元素进行计算,直到运算符栈为空,操作数栈中只剩下一个元素,即为表达式的值。
以上代码实现了对算术表达式的求值,可以通过终端输入一个合法的、不含变量的算术表达式,并输出该表达式的值。
阅读全文