完整代码||算术表达式求解（C++）_c++算数表达式求值代码

juster数据结构实验3：算术表达式求解（附完整代码）

---

1、项目概述

1.1项目目标和主要内容

项目目标：设计一个简单的算术表达式计算器。
开发平台：Visual Studio 2022 x64
语言：C++
主要内容：

【基本要求】

实现标准整数类型的四则运算表达式的求值（包含括号，可多层嵌入）.

【测试数据】

（30+270)/3-123
5+（9*（62-37）+15）*6
要求自行设计非法表达式，进行程序测试，以保证程序的稳定运行。

【实现提示】

可以设计以下辅助函数
status isNumber（char ReadInChar）； //视ReadInchar 是否是数字而返回 TRUE 或 FALSE 。
int TurnToInteger（char IntChar)； // 将字符’0’.’9’ 转换为整数 9

2、项目设计

2.1基本知识

1.算术表达式求值 ：参与运算的数据（即操作数）可以为整数或实数，运算符（即操作符）为+、-、、/（加、减、乘、除）等二元操作符，包括圆括号；如 ：
56+10-25=15 6+(5-4/2)*3=15
2.运算规则：
先乘除，后加减，从左到右计算，先括号内，后括号外；
3.表达式：
中缀表达式 A+(B-C/D)E
中缀表达式 A+(B-C/D)E
例子：Exp= ab +(c-d/e)f
PostExp=abcde/-f+
4.

2.2使用方法：双栈算符优先级法

•双栈算符优先级法为了实现表达式求值，需要设置两个栈：
•一个是运算符栈op,用于寄存运算符；
•另一个成为操作数栈Opnd,用于寄存运算数和运算结果。


求值的处理过程是自左至右扫描表达式的每一个字符：
1、当扫描到的是运算数，则将其压入栈OPND，
2、当扫描到的是运算符时：
如这个运算符比OP栈顶运算符的优先级高，则入栈；
如这个运算符比OP栈顶运算符优先级低，则从OPND栈中弹出两个运算符，从栈OP中弹出栈顶运算符进行运算，并将运算结果压入栈OPND。
3、继续处理当前字符，直到遇到结束符为止。

3、程序运行结果

图3-1 测试运行结果

4、总结

4.1 项目的难点和关键点

1.理解和使用双栈法。
2.在此基础上，了解并使用单栈法。

4.2 心得体会

1.多去阅读相关的资料，看看别人的思路是怎么样。
2.多去请教老师、同学、会的人，学习他们怎么教，自己会了再去教别人。

5、参考文献

参考资料1
老师资料及网上资源等

6、项目源码

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

// 定义双向栈大小
#define DSTACK_SIZE 40

// 定义双向栈数据结构
typedef struct dStack_s
{
    int data[DSTACK_SIZE];
    unsigned top;          // 指向数据侧栈顶
    unsigned base;         // 指向运算符侧栈顶
}dStack_t;

// 函数声明
int expr(const char*);    // 计算函数

void stackInit(dStack_t**);     // 初始化函数
void operate(dStack_t*);        // 计算函数
int  IsOpr(char);                // 判断输入字符是否运算符
char Precede(char, char);        // 判断运算符的优先级
void PushNum(dStack_t*, int);   // 数字压栈
int  PopNum(dStack_t*);         // 数字出栈
int  GetTopNum(dStack_t*);      // 取数据侧栈顶数字
void PushOpr(dStack_t*, char);  // 运算符压栈
char PopOpr(dStack_t*);         // 运算符出栈
char GetTopOpr(dStack_t*);      // 取运算符侧栈顶运算符


void main(void)
{
    char* equation = NULL;
    char ch = 0;
    int i = 0;

    equation = (char*)malloc(DSTACK_SIZE * sizeof(char));
    if (NULL == equation)
    {
        printf("main:Insufficient Memory!\n");
        exit(0);
    }
    memset(equation, 0, DSTACK_SIZE * sizeof(char));

    printf("Input Formula: Exp. 3-7*（2+1）/2=\n");
    ch = getchar();
    for (i = 0; ch != '\n'; i++)
    {
        if (' ' == ch)   // 过滤掉等式中的空格，其他非法字符在后面检查
        {
            continue;
        }
        *(equation + i) = ch;
        ch = getchar();
    }
    *(equation + i) = '\0';

    printf("%d\n", expr(equation));
    free(equation);
}

/* 利用双向栈算法的计算函数 */
int expr(const char* equation)
{
    char ch = 0;
    int digit = 0;
    int flag = 0;        // 用于标识负号
    int finalKey = 0;    // 存放最后运算结果
    dStack_t* pdStack = NULL;

    if (NULL == equation)
    {
        printf("expr:Insufficient Memory!\n");
        exit(0);
    }

    stackInit(&pdStack);
    PushOpr(pdStack, '=');

    ch = *(equation++);
    if ('-' == ch)       // 特殊情况1：首字符为'-'，视为负号
    {
        ch = *(equation++);
        flag = 1;
    }
    while (ch != '=' || GetTopOpr(pdStack) != '=')  // 读入字符与运算符栈顶字符均为'='时结束运算
    {
        if (0 == IsOpr(ch))                  // 若输入为数字，可输入多位数
        {
            digit = ch - '0';
            ch = *(equation++);
            while (0 == IsOpr(ch))
            {
                digit = 10 * digit + ch - '0';
                ch = *(equation++);
            }
            if (1 == flag)
            {
                digit = -digit;
                flag = 0;
            }
            PushNum(pdStack, digit);
        }
        else if (1 == IsOpr(ch))
        {
            if (('-' == ch) && ('(' == *(equation - 2))) // 特殊情况2：若字符'-'紧接'('之后，视前者为负号
            {
                ch = *(equation++);
                flag = 1;
            }
            else
            {
                switch (Precede(GetTopOpr(pdStack), ch))  // 比较栈顶运算符和输入运算符的优先级
                {
                case '<':
                {
                    PushOpr(pdStack, ch);
                    ch = *(equation++);
                    break;
                }
                case '=':
                {
                    PopOpr(pdStack);
                    ch = *(equation++);
                    break;
                }
                case '>':
                {
                    operate(pdStack);
                    break;
                }
                default:
                {
                    printf("Anomaly Result!\n");
                    exit(0);
                }
                }
            }
        }
        else
        {
            printf("Illegal input!\n");
            exit(0);
        }
    }
    finalKey = GetTopNum(pdStack);
    free(pdStack);
    return finalKey;
}

/* 四则运算函数 */
void operate(dStack_t* stack)
{
    int key = 0;
    int topDigit = 0;
    int hypDigit = 0;
    if (NULL == stack)
    {
        printf("operate:Insufficient Memory!\n");
        exit(0);
    }

    topDigit = PopNum(stack);
    hypDigit = PopNum(stack);
    switch (PopOpr(stack))
    {
    case '+':
    {
        key = hypDigit + topDigit;
        break;
    }
    case '-':
    {
        key = hypDigit - topDigit;
        break;
    }
    case '*':
    {
        key = hypDigit * topDigit;
        break;
    }
    case '/':
    {
        if (0 == topDigit)
        {
            printf("Divisor cannot be zero!\n");
            exit(0);
        }
        key = hypDigit / topDigit;
        break;
    }
    default:
    {
        printf("Illegal Operator!\n");
        exit(0);
    }
    }
    PushNum(stack, key);
}

/* 双向栈初始化函数 */
void stackInit(dStack_t** stack)
{
    *stack = (dStack_t*)malloc(sizeof(dStack_t));
    if ((NULL == *stack) || (NULL == stack))
    {
        printf("stackInit:Insufficient Memory!\n");
        exit(0);
    }

    memset((*stack)->data, 0, DSTACK_SIZE * sizeof(int));
    (*stack)->top = -1;
    (*stack)->base = DSTACK_SIZE;
}

/* 数字压栈 */
void PushNum(dStack_t* stack, int digit)
{
    if (NULL == stack)
    {
        printf("PushNum:Insufficient Memory!\n");
        exit(0);
    }
    if (stack->top + 1 == stack->base)  // 判断是否栈满
    {
        printf("PushNum:Stack is full!\n");
        exit(0);
    }

    (stack->top)++;
    (stack->data)[stack->top] = digit;
}

/* 运算符压栈 */
void PushOpr(dStack_t* stack, char ch)
{
    int opr = (int)ch;
    if (NULL == stack)
    {
        printf("PushOpr:Insufficient Memory!\n");
        exit(0);
    }
    if (stack->top + 1 == stack->base)  // 判断是否栈满
    {
        printf("PushOpr:Stack is full!\n");
        exit(0);
    }

    (stack->base)--;
    (stack->data)[stack->base] = opr;
}

/* 数字出栈 */
int PopNum(dStack_t* stack)
{
    int digit = 0;
    if (NULL == stack)
    {
        printf("PopNum:Insufficient Memory!\n");
        exit(0);
    }
    if (-1 == stack->top)     // 判断栈数据侧是否空
    {
        printf("PopNum:Stack is empty!\n");
        exit(0);
    }

    digit = (stack->data)[stack->top];
    (stack->data)[stack->top] = 0;    // 栈内存清零，可删除此行代码
    (stack->top)--;
    return digit;
}

/* 运算符出栈 */
char PopOpr(dStack_t* stack)
{
    char opr = 0;
    if (NULL == stack)
    {
        printf("PopOpr:Insufficient Memory!\n");
        exit(0);
    }
    if (DSTACK_SIZE == stack->base)  // 判断栈运算符侧是否空
    {
        printf("PopOpr:Stack is empty!\n");
        exit(0);
    }

    opr = (char)(stack->data)[stack->base];
    (stack->data)[stack->base] = 0;  // 栈内存清零，可删除
    (stack->base)++;
    return opr;
}

/* 取数据侧栈顶数字 */
int GetTopNum(dStack_t* stack)
{
    if (NULL == stack)
    {
        printf("GetTopNum:Insufficient Memory!\n");
        exit(0);
    }
    if (-1 == stack->top)            // 判断栈运算符侧是否空
    {
        printf("PopOpr:Stack is empty!\n");
        return 0;
    }

    return (stack->data)[stack->top];
}

/* 取运算符侧栈顶运算符 */
char GetTopOpr(dStack_t* stack)
{
    if (NULL == stack)
    {
        printf("GetTopOpr:Insufficient Memory!\n");
        exit(0);
    }
    if (DSTACK_SIZE == stack->base)  // 判断栈运算符侧是否空
    {
        printf("GetTopOpr:Stack is empty!\n");
        return 0;
    }

    return ((char)(stack->data)[stack->base]);
}

/* 判断输入字符是否运算符：运算符返回1，数字返回0，其他字符返回-1 */
int IsOpr(char ch)
{
    if ('+' == ch || '-' == ch || '*' == ch || '/' == ch
        || '(' == ch || ')' == ch || '=' == ch)
    {
        return 1;
    }
    else if (ch >= '0' && ch <= '9')
    {
        return 0;
    }
    else
    {
        return -1;
    }
}

/* 判断运算符的优先级 */
char Precede(char aOpr, char bOpr)
{
    switch (aOpr)
    {
    case '+':
    case '-':
    {
        if ('*' == bOpr || '/' == bOpr || '(' == bOpr)
        {
            return '<';
        }
        else
        {
            return '>';
        }
    }           // 使用return返回，故不加break语句
    case '*':
    case '/':
    {
        if ('(' == bOpr)
        {
            return '<';
        }
        else
        {
            return '>';
        }
    }
    case '(':
    {
        if (')' == bOpr)
        {
            return '=';
        }
        else
        {
            return '<';
        }
    }
    case ')':            // 不会出现这种情况
    {
        return '>';
    }
    case '=':
    {
        if ('=' == bOpr)
        {
            return '=';
        }
        else
        {
            return '<';
        }
    }
    default:
    {
        exit(0);
    }
    }
}


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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409

注：资料来源于网络，侵权联系删除。