计算器算法的简单实现

无聊写着玩玩，顺便分享一下，有错误的地方欢迎指正，共同进步！

先把完整的代码贴上：

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
namespace Calculator
{
    class Program
    {
        const char ADDSYMBOL = '+';
        const char SUBSYMBOL = '-';
        const char DIVSYMBOL = '/';
        const char MULSYMBOL = '*';
 
        const char ONE = '1';
        const char TWO = '2';
        const char THREE = '3';
        const char FOUR = '4';
        const char FIVE = '5';
        const char SIX = '6';
        const char SEVEN = '7';
        const char EIGHT = '8';
        const char NINE = '9';
        const char ZERO = '0';
 
        const char LEFTBRACKET = '(';
        const char RIGHTBRACKET = ')';
 
        public Stack<int> numberStack = new Stack<int>();
        public Stack<char> symbolStack = new Stack<char>();
 
        public Stack<int> firstNumberStack = new Stack<int>();
        public Stack<char> firstSymbolStack = new Stack<char>();
 
        public Stack<int> secondNumberStack = new Stack<int>();
        public Stack<char> secondSymbolStack = new Stack<char>();
 
        static void Main(string[] args)
        {
            Program p = new Program();
            string expression = "2 + (3 +( 3 *4 - 5 / ( 2 +3))*4 - 6) + 6";
            int ret = p.Calculate(expression);
            Console.WriteLine(ret);
        }
 
        int Calculate(string expression)
        {
            bool numberStart = false;
            StringBuilder numberStr = new  StringBuilder();
            char[] expressionCharArray = expression.ToCharArray();
            for (int i = 0; i < expressionCharArray.Length; i++ )
            {
                char c = expressionCharArray[i];
                #region push the number to stack
                switch (ParseCharOfCharacterType(c))
                {
                    case CharacterType.NUMBER:
                        numberStart = true;
                        numberStr.Append(c);
                        if (i == expressionCharArray.Length - 1)//如果是最后一个字符那么也应该计算出数字并入栈
                        {
                            int num = 0;
                            if (int.TryParse(numberStr.ToString(), out num))
                            {
                                numberStack.Push(num);
                                numberStart = false;
                                numberStr.Clear();
                            }
                            else
                            {
                                Console.WriteLine("非法数字!");
                                return 0;
                            }
                        }
                        break;
                    case CharacterType.OPERATOR:
                    case CharacterType.PORIORITYSIGN:
                        if (numberStart)
                        {
                            int num = 0;
                            if (int.TryParse(numberStr.ToString(), out num))
                            {
                                numberStack.Push(num);
                                numberStart = false;
                                numberStr.Clear();
                            }
                            else
                            {
                                Console.WriteLine("非法数字!");
                                return 0;
                            }
                        }
                        break;
                }
                #endregion
 
                switch (ParseCharOfCharacterType(c))
                {
                    case CharacterType.OPERATOR:
                        symbolStack.Push(c);
                        break;
                    case CharacterType.PORIORITYSIGN:
                        switch (c)
                        {
                            case LEFTBRACKET:
                                symbolStack.Push(c);
                                break;
                            case RIGHTBRACKET:
                                firstNumberStack.Push(numberStack.Pop());
                                while (symbolStack.Peek() != LEFTBRACKET)
                                {
                                    firstSymbolStack.Push(symbolStack.Pop());
                                    firstNumberStack.Push(numberStack.Pop());
                                }
                                symbolStack.Pop();// 移除左括号
                                DoP1Calculator();
                                DoP2Calculator();
                                break;
                        }
                        break;
                }
            }
 
            // 当运行到这里时，整个表达式没有任何括号了
            firstNumberStack.Push(numberStack.Pop());
            while (symbolStack.Count > 0)
            {
                firstSymbolStack.Push(symbolStack.Pop());
                firstNumberStack.Push(numberStack.Pop());
            }
            DoP1Calculator();
            DoP2Calculator();
            return numberStack.Pop();
        }
 
        void DoP1Calculator()
        {
            // 这个方法只处理表达式的乘法和除法:
            // 以这个算式为例3 *4 - 5 / 5，最后的结果为
            // 12 - 1
            secondNumberStack.Push(firstNumberStack.Pop());
            while (firstSymbolStack.Count > 0)
            {
                switch (firstSymbolStack.Peek())
                {
                    case ADDSYMBOL:
                    case SUBSYMBOL:
                        secondNumberStack.Push(firstNumberStack.Pop());
                        secondSymbolStack.Push(firstSymbolStack.Pop());
                        break;
                    case MULSYMBOL:
                        int leftValue = secondNumberStack.Pop();
                        int rightValue = firstNumberStack.Pop();
                        int ret = leftValue * rightValue;
                        firstSymbolStack.Pop(); // 移除乘号
                        secondNumberStack.Push(ret);
                        break;
                    case DIVSYMBOL:
                        int leftVal = secondNumberStack.Pop();
                        int rightVal = firstNumberStack.Pop();
                        int retVal = leftVal / rightVal;
                        firstSymbolStack.Pop(); // 移除除号
                        secondNumberStack.Push(retVal);
                        break;
                }
            }
        }
 
        void DoP2Calculator()
        {
            secondNumberStack = StackUtil<int>.ReverseStack(secondNumberStack);
            secondSymbolStack = StackUtil<char>.ReverseStack(secondSymbolStack);
            while (secondSymbolStack.Count > 0)
            {
                int leftValue = secondNumberStack.Pop();
                int rightValue = secondNumberStack.Pop();
                switch (secondSymbolStack.Pop())
                {
                    case ADDSYMBOL:
 
                        secondNumberStack.Push(leftValue + rightValue);
                        break;
                    case SUBSYMBOL:
                        secondNumberStack.Push(leftValue - rightValue);
                        break;
                }
            }
            numberStack.Push(secondNumberStack.Pop());
        }
        CharacterType ParseCharOfCharacterType(char c)
        {
            CharacterType ret = CharacterType.UNKNOWN;
            switch (c)
            {
                case ADDSYMBOL: ret = CharacterType.OPERATOR; break;
                case SUBSYMBOL: ret = CharacterType.OPERATOR; break;
                case DIVSYMBOL: ret = CharacterType.OPERATOR; break;
                case MULSYMBOL: ret = CharacterType.OPERATOR; break;
                case ONE: ret = CharacterType.NUMBER; break;
                case TWO: ret = CharacterType.NUMBER; break;
                case THREE: ret = CharacterType.NUMBER; break;
                case FOUR: ret = CharacterType.NUMBER; break;
                case FIVE: ret = CharacterType.NUMBER; break;
                case SIX: ret = CharacterType.NUMBER; break;
                case SEVEN: ret = CharacterType.NUMBER; break;
                case EIGHT: ret = CharacterType.NUMBER; break;
                case NINE: ret = CharacterType.NUMBER; break;
                case ZERO: ret = CharacterType.NUMBER; break;
                case LEFTBRACKET: ret = CharacterType.PORIORITYSIGN; break;
                case RIGHTBRACKET: ret = CharacterType.PORIORITYSIGN; break;
                default: ret = CharacterType.UNKNOWN; break;
            }
 
            return ret;
        }
    }
 
    public enum CharacterType
    {
        NUMBER =0,
        OPERATOR = 1,
        PORIORITYSIGN = 2,
        UNKNOWN = 3
    }
 
    public class StackUtil<T>
    {
        public static Stack<T> ReverseStack(Stack<T> stack)
        {
            Stack<T> ret = new Stack<T>();
            while (stack.Count > 0)
            {
                ret.Push(stack.Pop());
            }
            return ret;
        }
    }
}

当拿到一个字符串算术表达式时，先把数字压入数字栈numerStack，四则运算符和左括号压入符号栈symbolStack.但是当遇到右括号是我们需要把这个右括号和这之前的第一个左括号之间的表达式计算出来然后把计算结果代入到此对括号的位置。如何计算这个表达式先不考虑，这个时候你可以不去看DoP1Calculator和DoP2Calculator这2个方法，而且代码只看前117行。

以我的例子为例: 当第一次运行完103到113之间的代码，整个算术表达式变为: 2 + (3 +( 3 *4 - 5 / 5)*4 - 6) + 6

第二次变为：2 + (3 +11 * 4 - 6) + 6以此类推。

当整个for循环结束后，最后的表达式只剩下了四则运算，没有任何的括号。那么计算这个又和计算括号里的算式是一样的问题。所以我们现在只要解决这个问题就可以了。

接下来我们看DoP1Calculator方法，以处理3 4 - 5 / 5为例：这个时候firstNumberStack的结构是3，4，5，5；firstSymbolStack的结构是,-，/;首先我们把第一个数3压入secondNumberStack,然后看第一个运算符是什么。如果没有运算符，那么运算结束。

在这里我们一看是乘法，我们需要计算。我们取出刚刚压入secondNumberStack的数3，然后取出firstNumberStack的第一个数4，进行计算后压入secondNumberStack。这个时候，firstNumberStack的结构是5，5；firstSymbolStack的结构是-,/;secondNumberStack的结构是12；

再循环一次，我们看到的运算符是减法，那么我们不运算，分别把5，-压入secondNumberStack和secondSymbolStack；这个时候firstNumberStack的结构是5;firstSymbolStack的结构是/；secondNumberStack的结构是12,5;secondSymbolStack的结构是-；

再循环一次，我们看到的运算符是除法，需要运算。我们取出再上一步压入secondNumberStack的5和在firstNumberStack的第一个数5（在这里例子里其实也已经是最后一个数了）进行运算。把结果压入secondNumberStack。这个时候secondNumberStack的结构为:1,12;secondSymbolStack为-；firstNumberStack和firstSymbolStack都已经为空。

最后我们进入DoP2Calculator方法。根据上面的解释，可以很清晰的看到我们把12 - 1的结果重新压入到最初的括号的位置。