今天看到了校內上一個batman equation，覺得很順不舒服。第一個是因為我覺得那個圖是錯的，第二個是因為這讓我開始思考如何對任意的f(x, y)進行繪制。其實這是個很困難的問題。但是如果我假設f(x, y)是處處可微的，那麼問題說不定會簡單一點。因此今天晚上就忍不住開始寫了。我的想法是，對於屏幕上的所有點，分別令x或者y等於該點的其中一個坐標元素，對f(x, y)的的另一個自變量做牛頓迭代法。這樣所有的點最後就會收斂到一個點集，然後我把它畫出來，大概就是函數圖象了吧。
不過因為開始思考的時候已經晚了，所以今天就只寫了一點點代碼，用C#，可以在Vczh Library++3.0的Candidate\Games\FunctionVisualizer找到（啊，我就是喜歡把代碼都往Candidate裡面塞）。現在完成的有，對於一個可以包含空格的表達式e，我把它語法分析稱語法樹，然後再對x和y求導，就得到了三顆語法樹。然後我對他進行化簡，就得到了六棵語法樹。當然這個化簡只是簡單的，並沒有對函數的組合進行處理。
偉大的C#也是可以用指針的，啊哈哈哈哈，下面是語法分析的代碼： 1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using FvCalculation.OperatorExpressions;
6 using FvCalculation.PrimitiveExpressions;
7
8 namespace FvCalculation
9 {
10 unsafe static class ExpressionParser
11 {
12 private static void SkipSpaces(char** input)
13 {
14 while (char.IsWhiteSpace(**input))
15 {
16 (*input)++;
17 }
18 }
19
20 private static bool Char(char** input, char c)
21 {
22 SkipSpaces(input);
23 if (**input == c)
24 {
25 (*input)++;
26 return true;
27 }
28 else
29 {
30 return false;
31 }
32 }
33
34 private static double Number(char** input)
35 {
36 SkipSpaces(input);
37 bool dotted = false;
38 string s = "";
39 while (true)
40 {
41 if ('0' <= **input && **input <= '9')
42 {
43 s += **input;
44 (*input)++;
45 }
46 else if ('.' == **input && !dotted)
47 {
48 dotted = true;
49 s += **input;
50 (*input)++;
51 }
52 else
53 {
54 break;
55 }
56 }
57 if (s == "")
58 {
59 return double.NaN;
60 }
61 else
62 {
63 return double.Parse(s);
64 }
65 }
66
67 private static string Name(char** input)
68 {
69 SkipSpaces(input);
70 string s = "";
71 while (true)
72 {
73 if (('a' <= **input && **input <= 'z') || ('A' <= **input && **input <= 'Z') || ('_' == **input) || (s != "" && '0' <= **input && **input <= '9'))
74 {
75 s += **input;
76 (*input)++;
77 }
78 else
79 {
80 break;
81 }
82 }
83 return s == "" ? null : s;
84 }
85
86 private static Expression Exp0(char** input)
87 {
88 if (Char(input, '('))
89 {
90 Expression e = Exp3(input);
91 if (!Char(input, ')'))
92 {
93 throw new ArgumentException("Error encountered, at " + new string(*input));
94 }
95 return e;
96 }
97 else if (Char(input, '-'))
98 {
99 return new NegExpression
100 {
101 Op = Exp0(input),
102 };
103 }
104 else
105 {
106 double number = Number(input);
107 if (!double.IsNaN(number))
108 {
109 return new NumberExpression
110 {
111 Number = number,
112 };
113 }
114
115 string name = Name(input);
116 if (name == null)
117 {
118 throw new ArgumentException("Error encountered, at " + new string(*input));
119 }
120
121 if (!Char(input, '('))
122 {
123 return new VariableExpression
124 {
125 Name = name,
126 };
127 }
128
129 FunctionExpression f = FunctionExpression.FromName(name);
130 f.Op = Exp3(input);
131 if (!Char(input, ')'))
132 {
133 throw new ArgumentException("Error encountered, at " + new string(*input));
134 }
135 return f;
136 }
137 }
138
139 private static Expression Exp1(char** input)
140 {
141 Expression e = Exp0(input);
142 while (true)
143 {
144 if (Char(input, '^'))
145 {
146 e = new PowerExpression
147 {
148 Left = e,
149 Right = Exp0(input),
150 };
151 }
152 else
153 {
154 break;
155 }
156 }
157 return e;
158 }
159
160 private static Expression Exp2(char** input)
161 {
162 Expression e = Exp1(input);
163 while (true)
164 {
165 if (Char(input, '*'))
166 {
167 e = new MulExpression
168 {
169 Left = e,
170 Right = Exp1(input),
171 };
172 }
173 else if (Char(input, '/'))
174 {
175 e = new DivExpression
176 {
177 Left = e,
178 Right = Exp1(input),
179 };
180 }
181 else
182 {
183 break;
184 }
185 }
186 return e;
187 }
188
189 private static Expression Exp3(char** input)
190 {
191 Expression e = Exp2(input);
192 while (true)
193 {
194 if (Char(input, '+'))
195 {
196 e = new AddExpression
197 {
198 Left = e,
199 Right = Exp2(input),
200 };
201 }
202 else if (Char(input, '-'))
203 {
204 e = new SubExpression
205 {
206 Left = e,
207 Right = Exp2(input),
208 };
209 }
210 else
211 {
212 break;
213 }
214 }
215 return e;
216 }
217
218 private static Expression UnsafeParse(char* input)
219 {
220 Expression result = Exp3(&input);
221 if ((int)*input == 0)
222 {
223 return result;
224 }
225 else
226 {
227 throw new ArgumentException("Expression contains unparsed tail, at " + new string(input));
228 }
229 }
230
231 public static Expression Parse(string s)
232 {
233 fixed (char* input = s.Trim())
234 {
235 return UnsafeParse(input);
236 }
237 }
238 }
239 }
240
下面是運行結果： 1 input: 1
2 parse: 1
3 reparse: 1
4 simplified: 1
5 contains x: False
6 contains y: False
7 dx: 0
8 dy: 0
9 simplified dx: 0
10 simplified dy: 0
11
12 input: 1.2
13 parse: 1.2
14 reparse: 1.2
15 simplified: 1.2
16 contains x: False
17 contains y: False
18 dx: 0
19 dy: 0
20 simplified dx: 0
21 simplified dy: 0
22
23 input: -3
24 parse: -3
25 reparse: -3
26 simplified: -3
27 contains x: False
28 contains y: False
29 dx: -0
30 dy: -0
31 simplified dx: 0
32 simplified dy: 0
33
34 input: 12+34
35 parse: (12 + 34)
36 reparse: (12 + 34)
37 simplified: 46
38 contains x: False
39 contains y: False
40 dx: (0 + 0)
41 dy: (0 + 0)
42 simplified dx: 0
43 simplified dy: 0
44
45 input: 56*78
46 parse: (56 * 78)
47 reparse: (56 * 78)
48 simplified: 4368
49 contains x: False
50 contains y: False
51 dx: ((0 * 78) + (56 * 0))
52 dy: ((0 * 78) + (56 * 0))
53 simplified dx: 0
54 simplified dy: 0
55
56 input: x^y
57 parse: (x ^ y)
58 reparse: (x ^ y)
59 simplified: (x ^ y)
60 contains x: True
61 contains y: True
62 dx: (y * (x ^ (y - 1)))
63 dy: ((x ^ y) * ln(x))
64 simplified dx: (y * (x ^ (y - 1)))
65 simplified dy: ((x ^ y) * ln(x))
66
67 input: x+2*y+4
68 parse: ((x + (2 * y)) + 4)
69 reparse: ((x + (2 * y)) + 4)
70 simplified: ((x + (2 * y)) + 4)
71 contains x: True
72 contains y: True
73 dx: ((1 + ((0 * y) + (2 * 0))) + 0)
74 dy: ((0 + ((0 * y) + (2 * 1))) + 0)
75 simplified dx: 1
76 simplified dy: 2
77
78 input: (x+y)*(3+4)
79 parse: ((x + y) * (3 + 4))
80 reparse: ((x + y) * (3 + 4))
81 simplified: ((x + y) * 7)
82 contains x: True
83 contains y: True
84 dx: (((1 + 0) * (3 + 4)) + ((x + y) * (0 + 0)))
85 dy: (((0 + 1) * (3 + 4)) + ((x + y) * (0 + 0)))
86 simplified dx: 7
87 simplified dy: 7
88
89 input: exp(x+y)
90 parse: exp((x + y))
91 reparse: exp((x + y))
92 simplified: exp((x + y))
93 contains x: True
94 contains y: True
95 dx: (exp((x + y)) * (1 + 0))
96 dy: (exp((x + y)) * (0 + 1))
97 simplified dx: exp((x + y))
98 simplified dy: exp((x + y))
99
100 input: x+ln(y)
101 parse: (x + ln(y))
102 reparse: (x + ln(y))
103 simplified: (x + ln(y))
104 contains x: True
105 contains y: True
106 dx: (1 + (0 / y))
107 dy: (0 + (1 / y))
108 simplified dx: 1
109 simplified dy: (1 / y)
110
111 input: x/y
112 parse: (x / y)
113 reparse: (x / y)
114 simplified: (x / y)
115 contains x: True
116 contains y: True
117 dx: (((1 * y) - (x * 0)) / (y ^ 2))
118 dy: (((0 * y) - (x * 1)) / (y ^ 2))
119 simplified dx: (y / (y ^ 2))
120 simplified dy: (-x / (y ^ 2))
121
122 input: exp(x)/ln(x)
123 parse: (exp(x) / ln(x))
124 reparse: (exp(x) / ln(x))
125 simplified: (exp(x) / ln(x))
126 contains x: True
127 contains y: False
128 dx: ((((exp(x) * 1) * ln(x)) - (exp(x) * (1 / x))) / (ln(x) ^ 2))
129 dy: ((((exp(x) * 0) * ln(x)) - (exp(x) * (0 / x))) / (ln(x) ^ 2))
130 simplified dx: (((exp(x) * ln(x)) - (exp(x) * (1 / x))) / (ln(x) ^ 2))
131 simplified dy: 0
132
133 請按任意鍵繼續. . .
最後一個simplified dy化簡得真徹底啊……
