数据结构与算法——栈 表达式求值

 1 #pragma once
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 
 5 #define MAXSIZE 100
 6 #define MaxSize 128        //预先分配空间，这个数值根据实际需要预估确定
 7 
 8 typedef int ElemType;
 9 
10 typedef struct _SqStack
11 {
12     ElemType *base; //栈底指针
13     ElemType *top; //栈顶指针
14 }SqStack;
15 
16 bool InitStack(SqStack &S)                //构造一个空栈 S
17 {
18     S.base = new ElemType[MaxSize];        //为顺序栈分配一个最大容量为 Maxsize 的空间
19     if (!S.base)                        //空间分配失败
20         return false;
21     S.top=S.base;                        //top 初始为 base，空栈
22     return true;
23 }
24 
25 bool PushStack(SqStack &S, ElemType e)    // 插入元素 e 为新的栈顶元素
26 {
27     if (S.top-S.base == MaxSize)        //栈满
28         return false;
29     *(S.top++) = e;                        //元素 e 压入栈顶，然后栈顶指针加 1，等价于*S.top=e;
30     S.top++;
31     return true;
32 }
33 
34 bool PopStack(SqStack &S, ElemType &e)    //删除 S 的栈顶元素，暂存在变量 e中
35 {
36     if (S.base == S.top)                //栈空
37     {
38         return false;
39     }
40     e = *(--S.top);                        //栈顶指针减 1，将栈顶元素赋给 e
41     
42     return true;
43 }
44 
45 ElemType* GetTop(SqStack &S)            //返回 S 的栈顶元素，栈顶指针不变
46 {
47     if (S.top != S.base)                //栈非空
48     {
49         return S.top - 1;                //返回栈顶元素的值，栈顶指针不变
50     }
51     else
52     {
53         return NULL;
54     }
55 }
56 
57 int GetSize(SqStack &S)                    //返回栈中元素个数
58 {
59     return (S.top-S.base);
60 }
61 
62 bool IsEmpty(SqStack &S)                //判断栈是否为空
63 {
64     if (S.top == S.base)
65     {
66         return true;
67     }
68     else
69     {
70         return false;
71     }
72 }
73 
74 void DestoryStack(SqStack &S)            //销毁栈
75 {
76     if(S.base)
77     {
78         free(S.base);
79         S.base = NULL;
80         S.top = NULL;
81     }
82 }

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include "expression.h"
  4 
  5 using namespace std;
  6 
  7 //比较 lhs 的优先级是否不高于 rhs，rhs 表示栈顶的符号
  8 bool isLarger(const int& lhs, const int& rhs)
  9 {
 10     if ((rhs == ‘+‘ || rhs == ‘-‘) && (lhs == ‘*‘ || lhs == ‘/‘))
 11     {
 12         return true;
 13     }
 14     return false;
 15 }
 16 
 17 int operate(int left, int right, int op)        //对运算符求值
 18 {
 19     int result = 0;
 20     cout << "left:" << left << " right:" << right << (char)op << endl;
 21 
 22     switch (op)
 23     {
 24     case ‘+‘:
 25         result = left + right;
 26         break;
 27     case ‘-‘:
 28         result = left - right;
 29         break;
 30     case ‘*‘:
 31         result = left * right;
 32         break;
 33     case ‘/‘:
 34         result = left / right;
 35         break;
 36     default:
 37         break;
 38     }
 39     cout << "result: " << result << endl;
 40     return result;
 41 }
 42 
 43 int calculate(string input)
 44 {
 45     SqStack data_stack;                //操作数堆栈
 46     SqStack opt_stack;                //运算符堆栈
 47     int status = 0;                    //0-接受左操作数 1-接受运算符 "+-*/" 2-接受右操作数
 48     int ldata = 0, rdata = 0;
 49     char last_opt = ‘\0‘;
 50 
 51     //初始化栈：操作数和操作符
 52     InitStack(data_stack);
 53     InitStack(opt_stack);
 54 
 55     for (int i = 0; i < input.length(); i++)
 56     {
 57         if (isspace(input[i])) continue;                //空格键等忽略掉
 58         switch (status)
 59         {
 60         case 0:
 61             if (isdigit(input[i]))
 62             {
 63                 ldata *= 10;
 64                 ldata += input[i] - ‘0‘;
 65             }
 66             else
 67             {
 68                 cout << "得到左操作数:" << ldata << endl;
 69                 PushStack(data_stack, ldata);            //左操作数入栈
 70                 i--;
 71                 status = 1;
 72             }
 73             break;
 74 
 75         case 1:
 76             if (input[i] == ‘+‘ || input[i] == ‘-‘ || input[i] == ‘*‘ || input[i] == ‘/‘)
 77             {
 78                 if (IsEmpty(opt_stack))                            //第一个运算符,暂时不做任何处理，运算符先入栈保存
 79                 {
 80                     cout << "符号栈为空" << endl;
 81                     PushStack(opt_stack, input[i]);                //操作符入栈
 82                     cout << "符号" << (char)input[i] << "入栈" << endl;
 83                     status = 2;
 84                 }
 85                 else
 86                 {//非第一个运算符，则与之前的运算符比较优先级
 87                     cout << "isLarger:" << (char)(*GetTop(opt_stack)) << "&" << input[i] << endl;
 88                     if (isLarger(input[i], *GetTop(opt_stack)))
 89                     {
 90                         cout << "true" << endl;
 91                         PushStack(opt_stack, input[i]);            //操作符入栈
 92                         cout << "符号" << (char)input[i] << "入栈" << endl;
 93                         status = 2;
 94                         rdata = 0;
 95                     }
 96                     else
 97                     {//当前运算符的优先级不高于前一个运算符，则计算前一个运算符的值
 98                         int left = 0, right = 0;
 99                         int opt;
100                         cout << "false" << endl;
101                         do
102                         {
103                             PopStack(data_stack, right);
104                             PopStack(data_stack, left);
105                             PopStack(opt_stack, opt);
106                             cout << "符号" << (char)opt << "出栈" << endl;
107                             cout << "计算前一个运算符" << (char)opt << endl;
108                             int result = operate(left, right, opt);
109                             PushStack(data_stack, result);
110                         } while (!IsEmpty(opt_stack) && !isLarger(input[i], *GetTop(opt_stack)));
111                         PushStack(opt_stack, input[i]);
112                         cout << "符号" << (char)input[i] << "入栈" << endl;
113                         status = 2;
114                         rdata = 0;
115                     }
116                 }
117             }
118             else if (input[i] == ‘=‘)
119             {//计算结果
120                 int opt, result;
121                 do
122                 {
123                     PopStack(data_stack, rdata);
124                     PopStack(data_stack, ldata);
125                     PopStack(opt_stack, opt);
126                     result = operate(ldata, rdata, opt);
127                     PushStack(data_stack, result);
128                 } while (!IsEmpty(opt_stack));
129 
130                 return result;
131             }
132             else
133             {
134                 cerr << "输入运算符错误！" << endl;
135             }
136             break;
137 
138         case 2:
139             if (isdigit(input[i]))
140             {
141                 rdata *= 10;
142                 rdata += input[i] - ‘0‘;
143             }
144             else
145             {
146                 cout << "得到右操作数:" << rdata << endl;
147                 PushStack(data_stack, rdata);            //右操作数入栈
148                 i--; status = 1;
149             }
150             break;
151         }
152     }
153     return -1;//最后的结果为栈顶元素
154 }
155 
156 int main(int argc, char const* argv[])
157 {
158     string str = "12+3*6/3+4*5=";
159     cout << calculate(str) << endl;
160     system("pause");
161     return 0;
162 }