表达式计算

表达式计算是实现程序设计逻辑语言的基本问题之一，也是栈和队列应用的一个典型例
子。该设计是先通过栈将中缀表达式转换为后缀表达式，在转换过程中又用到了队列的操作。而在得到后缀表达式之后，又用到队列的操作对生成的后缀表达式进行计算。在整个设计的实现过程中，用到的都是栈和队列的概念。

设计要求

以字符序列的形式从终端输入语法正确的、不含变量的算术表达式（整数和实数都要考虑），利用给定的算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值过程中运算符栈、操作数栈、输入字符和主要操作的变化过程。
例如：

  • 输入25*(12-27/3)+2*5=
  • 则程序运行后输出25*(12-27/3)+2*5=85
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>
#define MAX_SIZE 100
// 定义运算符栈结构
typedef struct {
    char items[MAX_SIZE];
    int top;
} OperatorStack;
// 定义操作数栈结构
typedef struct {
    double items[MAX_SIZE];
    int top;
} OperandStack;
// 初始化运算符栈
void initOperatorStack(OperatorStack* stack) {
    stack->top = -1;
}
// 初始化操作数栈
void initOperandStack(OperandStack* stack) {
    stack->top = -1;
}
// 检查栈是否为空
bool isEmpty(OperatorStack* stack) {
    return stack->top == -1;
}
// 检查栈是否满
bool isFull(OperatorStack* stack) {
    return stack->top == MAX_SIZE - 1;
}
// 入栈
void pushOperator(OperatorStack* stack, char item) {
    if (!isFull(stack)) {
        stack->items[++stack->top] = item;
    }
    else {
        printf("Error: Operator stack overflow\n");
        exit(EXIT_FAILURE);
    }
}
// 出栈
char popOperator(OperatorStack* stack) {
    if (!isEmpty(stack)) {
        return stack->items[stack->top--];
    }
    else {
        printf("Error: Operator stack underflow\n");
        exit(EXIT_FAILURE);
    }
}
// 获取栈顶元素
char peekOperator(OperatorStack* stack) {
    if (!isEmpty(stack)) {
        return stack->items[stack->top];
    }
    else {
        printf("Error: Operator stack is empty\n");
        exit(EXIT_FAILURE);
    }
}
// 入栈
void pushOperand(OperandStack* stack, double item) {
    if (!isFull(stack)) {
        stack->items[++stack->top] = item;
    }
    else {
        printf("Error: Operand stack overflow\n");
        exit(EXIT_FAILURE);
    }
}
// 出栈
double popOperand(OperandStack* stack) {
    if (!isEmpty(stack)) {
        return stack->items[stack->top--];
    }
    else {
        printf("Error: Operand stack underflow\n");
        exit(EXIT_FAILURE);
    }
}
// 获取栈顶元素
double peekOperand(OperandStack* stack) {
    if (!isEmpty(stack)) {
        return stack->items[stack->top];
    }
    else {
        printf("Error: Operand stack is empty\n");
        exit(EXIT_FAILURE);
    }
}
// 获取运算符的优先级
int precedence(char op) {
    switch (op) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return 0;
    }
}
// 执行算术运算
double evaluate(double operand1, double operand2, char op) {
    switch (op) {
    case '+':
        return operand1 + operand2;
    case '-':
        return operand1 - operand2;
    case '*':
        return operand1 * operand2;
    case '/':
        if (operand2 != 0) {
            return operand1 / operand2;
        }
        else {
            printf("Error: Division by zero\n");
            exit(EXIT_FAILURE);
        }
    default:
        printf("Error: Invalid operator\n");
        exit(EXIT_FAILURE);
    }
}
// 计算表达式的值
double calculate(char* expression) {
    OperatorStack operatorStack;
    OperandStack operandStack;
    initOperatorStack(&operatorStack);
    initOperandStack(&operandStack);
    char current;
    double operand1, operand2;
    char operator;
    for (int i = 0; expression[i] != '\0'; i++) {
        current = expression[i];
        if (isdigit(current) || current == '.') {
            double number = atof(&expression[i]);
            while (isdigit(expression[i]) || expression[i] == '.') {
                i++;
            }
            i--;
            pushOperand(&operandStack, number);
        }
        else if (current == '(') {
            pushOperator(&operatorStack, current);
        }
        else if (current == ')') {
            while (peekOperator(&operatorStack) != '(') {
                operand2 = popOperand(&operandStack);
                operand1 = popOperand(&operandStack);
                operator = popOperator(&operatorStack);
                pushOperand(&operandStack, evaluate(operand1, operand2, operator));
            }
            popOperator(&operatorStack); // 弹出左括号
        }
        else if (current == '+' || current == '-' || current == '*' || current == '/') {
            while (!isEmpty(&operatorStack) && precedence(peekOperator(&operatorStack)) >= precedence(current)) {
                operand2 = popOperand(&operandStack);
                operand1 = popOperand(&operandStack);
                operator = popOperator(&operatorStack);
                pushOperand(&operandStack, evaluate(operand1, operand2, operator));
            }
            pushOperator(&operatorStack, current);
        }
    }
    while (!isEmpty(&operatorStack)) {
        operand2 = popOperand(&operandStack);
        operand1 = popOperand(&operandStack);
        operator = popOperator(&operatorStack);
        pushOperand(&operandStack, evaluate(operand1, operand2, operator));
    }
    return peekOperand(&operandStack);
}
int main() {
    char expression[100];
    printf("输入算术表达式: ");
    fgets(expression, sizeof(expression), stdin);
    double result = calculate(expression);
    printf("结果: %s=%.2f\n", expression, result);
    return 0;
}

1
2
3
输入算术表达式: 25*(12-27/3)+2*5=
结果: 25*(12-27/3)+2*5=
=85.00