面試題 100 —— 5 查找 Top K
這里的做法是利用一個堆，用這個堆作為 K 個元素的輸出容器，堆的特點是可以以 O(1) 的效率去堆中最大/小的元素。
正式利用了這一點，這種方法的時間復雜度為 O(NlogK)
查找最小的 K 個數
利用最大堆
思路時，開始的時候堆為空，堆中元素個數還不足 K 個，所以遍歷的當前元素直接加入到堆中
當堆中元素等于 K 的時候，檢查當前元素與堆中最大元素的大小關系，若大于最大元素則忽略，否則將堆中最大元素刪除，并將當前元素添加到堆中。
整個過程，遍歷一遍集合，每次針對當前元素需要對堆進行調整，總的時間復雜度為 O(NlogK)
http://m.shnenglu.com/jake1036/archive/2011/05/16/146466.html
代碼實現：
1 #include <iostream>
2 #include <vector>
3 #include <set>
4 using namespace std;
5
6 typedef vector<int> dataset;
7 typedef multiset<int, greater<int> > bigheap;
8
9 void findTopK(bigheap& bh, const dataset& ds, int k)
10 {
11 bh.clear();
12 for (dataset::const_iterator cit = ds.begin(); cit != ds.end(); ++cit)
13 {
14 if (bh.size() < k)
15 {
16 bh.insert(*cit);
17 }
18 else
19 {
20 bigheap::iterator it = bh.begin();
21 if (*it > *cit)
22 {
23 bh.erase(it);
24 bh.insert(*cit);
25 }
26 }
27 }
28 }
29
30 int main()
31 {
32 dataset ds;
33 for (int i = 100; i != 0; --i)
34 {
35 ds.push_back(i);
36 }
37 bigheap bh;
38 findTopK(bh, ds, 10);
39 for (bigheap::const_iterator cit = bh.begin(); cit != bh.end(); ++cit)
40 {
41 cout << *cit << endl;
42 }
43 return 0;
44 }
45
46
posted @
2011-07-12 17:46 unixfy 閱讀(316) |
評論 (0) |
編輯 收藏：： 和同學聊了起來
=======================
信息論的角度去討論算法
一個算法的高效不高效
看它產生的信息量有多大
如果有冗余的信息量，效率就有提高的空間
舉個例子
你統計一個集合中重復出現的元素
那么久沒有必要對元素計數
直觀的方法是對元素計數
然后檢測
但是這個計數是冗余的
只需要找到重復的，不需要知道具體出現的次數
針對這個問題
我是覺得最高效的算法應該是恰恰能解決現有問題的算法，不生成多余的冗余信息
生成任何信息都是需要代價的
信息論。。。
算法的高效不高效，一是時間二是空間
上面那個問題，既然不需要計數
只需要給每個元素一個位，節省空間
位圖
海量數據的時候
如果 幾十億個 int 數
看里面是否存在重復的
重復出現的時候，檢測到對應為為 1 ，說明之前存在了
所以就是重復出現的數
遍歷這個集合
可以將結果存起來
我的意思是，這個問題就是找到重復出現的，沒有必要對每個數計數
這樣，就可以節省空間
還有時間的
還有就是充分挖掘問題中的信息
充分利用問題中的信息，提高獲取的信息量，充分利用了隱藏的信息量就會涉及出高效的算法
基于比較的算法，不會是 O(N) 的，最優就是 O(NlogN)。
基數排序、桶排序，這樣的就是有限制性的算法，這個限制就是元素有個范圍，限制是給了隱含的信息，利用這個可以就有了 O(N) 的排序
盡可能從問題中挖掘潛在的信息，獲得的信息越多越有利于解決問題，也就越有可能獲得高效的解法。
控制論、系統論、信息論
信息論是香農創建的，也屬于數學，算法就是解決問題的，解決問題的就是想得到結果，結果就是一種信息，算法的設計可以用信息論的角度解釋
反正總結起來是兩點吧，一是充分挖掘已有的信息，二是盡可能不要產生冗余信息。這樣設計的算法，既可以利用以存在的信息，也不會產生多余的信息，效率自然會高。
======================
FOO 21:57:39
信息論的角度去討論算法
FOO 21:57:57
一個算法的高效不高效
FOO 21:58:09
看它產生的信息量有多大
FOO 21:58:36
如果有冗余的信息量，效率就有提高的空間
BAR 22:00:18
額
FOO 22:00:53
呵呵
FOO 22:01:05
后面的幾句是我最近感受的
BAR 22:01:11
呵呵
BAR 22:01:14
我不懂
FOO 22:01:17
呃
BAR 22:01:20
我還是碼農級別的
FOO 22:01:23
呃
FOO 22:01:27
舉個例子
FOO 22:01:57
你統計一個集合中重復出現的元素
FOO 22:02:10
那么久沒有必要對元素計數
FOO 22:02:16
直觀的方法是對元素計數
FOO 22:02:27
然后檢測
FOO 22:02:38
但是這個計數是冗余的
FOO 22:02:51
只需要找到重復的，不需要知道具體出現的次數
FOO 22:02:55
針對這個問題
BAR 22:03:28
額
BAR 22:04:14
你繼續
BAR 22:04:11
FOO 22:04:24
我是覺得最高效的算法應該是恰恰能解決現有問題的算法，不生成多余的冗余信息
FOO 22:04:33
生成任何信息都是需要代價的
FOO 22:04:36
信息論。。。
BAR 22:04:41
你先說上面那個問題
FOO 22:06:05
算法的高效不搞笑，一是時間二是空間
FOO 22:06:14
上面那個問題，既然不需要計數
BAR 22:06:20
上面那個問題什么方法好？
FOO 22:06:29
只需要給每個元素一個位，節省空間
FOO 22:06:43
位圖吧
FOO 22:06:44
呵呵
BAR 22:06:50
那你怎么做
FOO 22:06:51
海量數據的時候
FOO 22:07:00
如果 幾十億個 int 數
BAR 22:07:08
把位置1
BAR 22:07:14
第二次出現呢
FOO 22:07:15
看里面是否存在重復的
BAR 22:07:20
也就是重復的時候出現呢
BAR 22:07:00
一個元素出現了一次
FOO 22:07:53
重復出現的時候，檢測到對應為為 1 ，說明之前存在了
BAR 22:08:00
是撒
FOO 22:08:03
所以就是重復出現的數
BAR 22:08:05
你只找一個么
FOO 22:08:11
所有
BAR 22:08:17
還是說你有另一個輸出結果的地方
FOO 22:08:22
遍歷這個集合
FOO 22:08:36
可以將結果存起來
BAR 22:08:41
就是出現重復的時候把這個重復的放到另外一個地方或者輸出
FOO 22:09:07
恩
BAR 22:09:22
恩，我先洗澡去了
FOO 22:09:31
我的意思是，這個問題就是找到重復出現的，沒有必要對每個數計數
FOO 22:09:36
這樣，就可以節省空間
FOO 22:09:51
還是時間的
FOO 22:14:58
還有就是充分挖掘問題中的信息
FOO 22:15:38
充分利用問題中的信息，提高獲取的信息量，充分利用了隱藏的信息量就會涉及出高效的算法
FOO 22:16:11
基于比較的算法，不會是 O(N) 的，最優就是 O(NlogN)。
FOO 22:17:09
基數排序、桶排序，這樣的就是有限制性的算法，這個限制就是元素有個范圍，限制是給了隱含的信息，利用這個可以就有了 O(N) 的排序
FOO 22:17:37
盡可能從問題中挖掘潛在的信息，獲得的信息越多越有利于解決問題，也就越有可能獲得高效的解法。
FOO 22:18:04
呵呵
FOO 22:18:23
控制論、系統論、信息論
FOO 22:19:47
信息論是香農創建的，也屬于數學，算法就是解決問題的，解決問題的就是想得到結果，結果就是一種信息，算法的設計可以用信息論的角度解釋，呃。。
FOO 22:21:24
反正總結起來是兩點吧，一是充分挖掘已有的信息，二是盡可能不要產生冗余信息。這樣設計的算法，既可以利用以存在的信息，也不會產生多余的信息，效率自然會高。
posted @
2011-07-11 23:18 unixfy 閱讀(216) |
評論 (0) |
編輯 收藏給一個字符串，找到連續的最長數字字符串的長度和地址
掃描一遍，類似最大連續子串的做法
1 #include <iostream>
2 #include <string>
3 #include <cctype>
4 using namespace std;
5
6 string foo(const string& str)
7 {
8 string ret, tmp;
9 string::size_type i, j, left, right;
10 i = 0;
11 j = 0;
12 left = right = 0;
13 bool first = true;
14 for (string::size_type k = 0; k != str.size(); ++k)
15 {
16 if (isdigit(str[k]))
17 {
18 if (first)
19 {
20 first = false;
21 i = k;
22 j = k;
23 }
24 else
25 {
26 j = k;
27 }
28 }
29 else
30 {
31 first = true;
32 if ((j - i) > (right - left))
33 {
34 left = i;
35 right = j;
36 }
37 i = j = k;
38 }
39 }
40 ret = str.substr(left, right - left + 1);
41 return ret;
42 }
43
44 int main()
45 {
46 string str;
47 while (cin >> str)
48 {
49 cout << foo(str) << endl;
50 }
51 return 0;
52 }
53
posted @
2011-07-11 14:31 unixfy 閱讀(163) |
評論 (0) |
編輯 收藏思路就是先排序，O(NlogN)
然后一次遍歷排序后的集合
在具體遍歷的過程中，需要有個策略
詳見代碼
需要有兩個相鄰的滑標，比較相鄰的元素是否相等
但是為了避免重復計入，需要設置一個標志位，來表示是否是組里面的第一個元素
如果相鄰的兩個元素不相等，則表示前面組檢測結束，需要檢查記錄這個組的集合是否為空
若不為空，則將其加入結果中，并且要情況這個輔助組和標志位
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 void foo(vector<vector<int> >& ret, const vector<int>& dataset)
7 {
8 ret.clear();
9 if (dataset.size() <= 1)
10 {
11 return;
12 }
13 vector<int>::size_type i, j;
14 bool f = false;
15 vector<int> tmp;
16 for (i = 0, j = 1; i != dataset.size() - 1; ++i, ++j)
17 {
18 if (dataset[i] == dataset[j])
19 {
20 if (!f)
21 {
22 f = true;
23 tmp.push_back(dataset[i]);
24 tmp.push_back(dataset[j]);
25 }
26 else
27 {
28 tmp.push_back(dataset[j]);
29 }
30 }
31 else
32 {
33 if (!tmp.empty())
34 {
35 ret.push_back(tmp);
36 tmp.clear();
37 f = false;
38 }
39 }
40 }
41 }
42
43 int main()
44 {
45 vector<int> dataset;
46 for (int i = 0; i < 10; ++i)
47 {
48 dataset.push_back(i);
49 }
50 dataset.push_back(5);
51 dataset.push_back(3);
52 dataset.push_back(5);
53 dataset.push_back(8);
54 sort(dataset.begin(), dataset.end());
55
56 vector<vector<int> > ret;
57 foo(ret, dataset);
58 for (vector<vector<int> >::size_type i = 0; i != ret.size(); ++i)
59 {
60 for (vector<int>::size_type j = 0; j != ret[i].size(); ++j)
61 {
62 cout << ret[i][j] << ' ';
63 }
64 cout << endl;
65 }
66
67 return 0;
68 }
69
posted @
2011-07-11 13:53 unixfy 閱讀(270) |
評論 (0) |
編輯 收藏一個字符串集合
{"...", "...", ... }
找到相同的字符串，這樣的字符串是：包含的字符相同，字符的個數也相同
解決方案：
先對每個字符串排序
然后對排完序的字符串整體排序
遍歷整個字符串集合，即可得到結果
1 #include <iostream>
2 #include <vector>
3 #include <map>
4 #include <string>
5 #include <algorithm>
6 using namespace std;
7
8 int main()
9 {
10 vector<string> data;
11 data.push_back("cafe");
12 data.push_back("baidu");
13 data.push_back("duiba");
14 data.push_back("thisone");
15 data.push_back("iseasy");
16 data.push_back("esayis");
17 data.push_back("siesay");
18 data.push_back("esaysi");
19
20 multimap<string, string> mem;
21 for (vector<string>::size_type i = 0; i != data.size(); ++i)
22 {
23 string tmp(data[i]);
24 sort(tmp.begin(), tmp.end());
25 mem.insert(make_pair(tmp, data[i]));
26 }
27 if (mem.size() <= 1)
28 {
29 return 0;
30 }
31 for (multimap<string, string>::const_iterator cit = mem.begin(); cit != mem.end(); ++cit)
32 {
33 cout << cit->first << '\t' << cit->second << endl;
34 }
35 cout << "===================" << endl;
36 multimap<string, string>::const_iterator cit1, cit2, cit3;
37 cit1 = mem.begin();
38 cit3 = cit1;
39 cit2 = ++cit3;
40 bool f = false;
41 while (cit2 != mem.end())
42 {
43 if (cit1->first == cit2->first)
44 {
45 if (!f)
46 {
47 f = true;
48 cout << cit1->first << '(' << cit1->second << ')' << '\t' << cit2->first << '(' << cit2->second << ')' << '\t';
49 }
50 else
51 {
52 cout << cit2->first << '(' << cit2->second << ')' << '\t';
53 }
54 }
55 else
56 {
57 if (f)
58 {
59 cout << endl;
60 f = false;
61 }
62 }
63 ++cit1;
64 ++cit2;
65 }
66 return 0;
67 }
68
posted @
2011-07-11 13:34 unixfy 閱讀(539) |
評論 (0) |
編輯 收藏Linux 內核編譯升級記錄
先是裝了個 VMware
然后再里面裝了個 CentOS
之后就是漫長的內核編譯升級
上周周四、周五兩天都在忙這個，但是最終沒有成功
內核編譯一次需要花費一個小時，在虛擬機里面
一開始編譯的時候，出現錯誤。
主要存在兩個錯誤，剛開始不知道為什么，也沒有對出現的問題進行解決，只是重新編譯，結果當然失敗
第一個運行錯誤是
“insmod: error inserting ‘/lib/dm-region-hash.ko”
Google 了一下，是因為 init 里存在重復行，vi 編輯刪除之
第二個錯誤是：
“Volume group "VolGroup00" not found”
Google 了一下，是因為 .config 文件的配置問題
需要將
General setup --->
enable deprecated sysfs features
勾選了
這兩個問題解決后，Linux 內核升級即可完成。
下面說一下具體的步驟：
1.
下載最新版本的 Linux 內核
http://www.kernel.org/
這里是 linux-2.6.37.6.tar.bz2
拷到 /usr/src
2.
加壓 *.tar.bz2
root# tar -jvxf linux-2.6.37.6.tar.bz2
3.
進入 linux-2.6.37.6 文件夾
# cd linux-2.6.37.6
# make clean
# make mvproper
4.
配置
make menuconfig
注意，就是這里要勾選
General setup --->
enable deprecated sysfs features
否則會造成
“Volume group "VolGroup00" not found”
錯誤
5.
編譯
# make all
6.
安裝
# make modules_install
# make install
7.
設置
# mkinitrd /boot/initrd-2.6.37.6.img 2.6.37.6
# cp arch/x86/boot/bzImage /boot/vmlinuz-2.6.37.6
# cp /usr/src/linux-2.6.37.6/System.map /boot/System.map-2.6.37.6
8. 修改默認啟動內核
# cat /etc/grub.conf
# vi /etc/grub.conf
將 default=1 修改為
default=0
9.
刪除多余行，這是編譯的一個小 bug ，造成出現重復行
會造成
“insmod: error inserting ‘/lib/dm-region-hash.ko”
的錯誤
# cp /boot/initrd-2.6.37.6.img /tmp/
# cd /tmp/
# mkdir newinitrd
# cd newinitrd
# zcat ../initrd-2.6.37.6.img | cpio -i
# ls
# vi init
刪除 init 中存在的重復
echo “Loading dm-region-hash.ko module”
insmod /lib/dm-region-hash.ko
兩行
保存
# find . | cpio -c -o > ../initrd
# cd ..
# gzip -9 < initrd > initrd-2.6.37.6.img
# ls
# mv /boot/initrd-2.6.37.6.img /home/
# cp initrd-2.6.37.6.img /boot/
# reboot
進入新內核后，查看新內核的版本
# uname -a
# uname -r
===================================================
下面是我在升級過程中的命令記錄 history
543 tar -jvxf linux-2.6.37.6.tar.bz2
544 clear
545 cd linux-2.6.37.6
546 ls
547 make clean
548 make mvproper
549 clear
550 make all
551 make clean
552 make mrporper
553 make menuconfig
554 make menuconfig
555 \
556 \
557 cd /usr/src/linux-2.6.37.6
558 ls
559 ls -a
560 make all
561 clear
562 make modules_install
563 make install
564 mkinitrd /boot/initrd-2.6.37.6.img 2.6.37.6
565 rm /boot/initrd-2.6.37.6.img
566 ls
567 ls /boot/
568 mkinitrd /boot/initrd-2.6.37.6.img 2.6.37.6
569 cp arch/x86/boot/bzImage /boot/vmlinuz-2.6.37.6
570 cp /usr/src/linux-2.6.37.6/System.map /boot/System.map-2.6.37.6
571 cat /etc/grub.conf
572 cp /boot/initrd-2.6.37.6.img /tmp/
573 cd /tmp/
574 rm -rf newinitrd/
575 mkdir newinitrd
576 cd newinitrd/
577 zcat ../initrd-2.6.37.6.img | cpio -i
578 ls
579 vi init
580 find . | cpio -c -o > ../initrd
581 cd ..
582 gzip -9 < initrd > initrd-2.6.37.6.img
583 ls
584 mv /boot/initrd-2.6.37.6.img /home/
585 cp initrd-2.6.37.6.img /boot/
586 reboot
587 uname -r
588 uname -a
589 uname -r
590 history
======================================================
網上查的資料，主要是第一個和第二個
http://www.linuxidc.com/Linux/2010-09/28735.htm
http://blog.csdn.net/douzi24/article/details/5781148
http://hi.baidu.com/mhlovejn/blog/item/7a4a55fe65de7488b801a020.html/
http://blog.csdn.net/cdsnmdl/article/details/3922513
http://www.cublog.cn/u/9483/showart_2524232.html
http://blog.csdn.net/do2jiang/article/details/4965967
http://my.chinaunix.net/space.php?uid=113544&do=blog&id=85646
http://m.shnenglu.com/momoxiao/archive/2010/06/26/118758.html
posted @
2011-07-11 11:22 unixfy 閱讀(466) |
評論 (1) |
編輯 收藏最短摘要的生成
這個問題在《編程之美》中提到過。前幾天百度三面的時候也問到了這個問題，當時沒有答上來。從新翻閱了一下《編程之美》。
直觀的解決方案是：
從文檔第一個詞開始遍歷，尋找后面的詞是否與關鍵詞數組匹配
然后從文檔第二個、第三個 ... 一直到最后一個詞遍歷
這個過程要記錄最短文摘的信息。
這個時間復雜度是 O(N ^ 2 * M)
N 是文檔的長度
M 是關鍵詞數組的大小
改進的方法是：
對于求的的一個文摘，記錄第一次出現關鍵詞的位置，然后直接移動到該關鍵詞，然后右邊的邊界再向后移動。
這個時間復雜度是 O(N)
這種方法也就是說維持了一個摘要滑動窗口，一遍掃描文檔即可得到相應的最短摘要。
摘要中的關鍵詞可以用一個隊列來存儲，因為摘要滑動窗口的左邊界和右邊界都是要從左到右移動的。所以隊列正好適用。另外還應該維持一個對應文摘滑動窗口中的關鍵詞出現的次數表。在做左右邊界移動時需要考量這個次數表所提供的信息。
posted @
2011-07-03 20:34 unixfy 閱讀(1096) |
評論 (0) |
編輯 收藏N 個元素的入棧出棧序列總共有多少種？
我們用 0 表示入棧，1 表示出棧
假設有 6 個元素：
則有
0 0 0 0 0 0 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1 0 1
還有其他位置的情況，總共有多種？
我們知道這是一個 12 位的序列
窮舉有 2 ^ 12 個序列，有的不能滿足棧的入棧和出棧邏輯
也就是說：
任何一個元素，首先需要里面有 6 個 0 和 6 個 1，然后再統計包括它在內的前的 0 個個數是否小于 1 的個數，如果小于則不符合
如果統計到第 12 個元素，如果符合，則是正確的序列。（時間上只需要檢測到第 11 個元素）
1 #include <iostream>
2 using namespace std;
3
4 bool test(int k, int n)
5 {
6 int count = 0;
7 int temp = k;
8 for (; temp != 0; temp &= temp - 1, ++count);
9 if (count != n)
10 {
11 return false;
12 }
13
14 int zero = 0;
15 int t = n + n - 1; // 只需要檢測到 n + n - 2 位
16 for (int i = 0; i < t; ++i)
17 {
18 if ((k & (1 << i)) == 0)
19 {
20 ++zero;
21 }
22 else
23 {
24 if (--zero < 0)
25 {
26 return false;
27 }
28 }
29 }
30 return true;
31 }
32
33 // n : 元素的個數
34 int foo(int n)
35 {
36 int t = 1 << (n + n);
37 int ret = 0;
38 for (int k = 0; k < t; ++k)
39 {
40 if (test(k, n))
41 {
42 ++ret;
43 // 輸出
44 cout << ret << ":" << endl;
45 for (int i = 0; i < n + n; ++i)
46 {
47 if ((k & (1 << i)) == 0)
48 {
49 cout << 0 << ' ';
50 }
51 else
52 {
53 cout << 1 << ' ';
54 }
55 }
56 cout << endl;
57 }
58 }
59 return ret;
60 }
61
62 int main()
63 {
64 int n;
65 while (cin >> n)
66 {
67 cout << foo(n) << endl;
68 }
69 return 0;
70 }
http://www.wming.com/a/articles/devlanguage/c/2011/0101/81478_%E6%8E%A8%E8%8D%90%E5%BC%BA%E5%A5%B8%E9%98%BF%E9%87%8C%E5%B7%B4%E5%B7%B4%E4%B8%80%E4%B8%AA%E7%AC%94%E8%AF%95%E9%A2%98.html
http://topic.csdn.net/u/20091017/01/37370E0B-A736-40A5-8839-D8D0B9FCAADA.html
http://hi.csdn.net/baihacker
http://hi.baidu.com/feixue
http://hi.baidu.com/jumay426/blog/item/50b1ca84b5198726c65cc3f8.html
http://m.shnenglu.com/life02/archive/2009/10/17/98851.html
posted @
2011-07-02 13:51 unixfy 閱讀(282) |
評論 (0) |
編輯 收藏
基本原理是一樣的，都是順序掃描中綴表達式，用一個操作符棧進行中間處理。
牽涉運算符優先級。
過去是按照是操作符還是操作數處理，對于操作符做比較混亂的邏輯判斷。
這里分別對操作數，加減乘除左括號右括號進行分別處理，邏輯更簡單。
程序的邏輯結構在于分解。
1 // 中綴轉后綴
2 // 原汁原味
3
4 #include <stdio.h>
5 #include <string.h>
6 #include <stdlib.h>
7 #define MAX 100
8
9 char* infixToPostfix(char postfix[], char infix[])
10 {
11 static char stack[MAX];
12 int top = 0, ch, i = 0, j = 0;
13 ch = infix[i++];
14 while (ch != '#')
15 {
16 switch (ch)
17 {
18 case '(':
19 stack[top++] = ch;
20 break;
21 case ')':
22 while (top > 0 && stack[top - 1] != '(')
23 {
24 postfix[j++] = stack[--top];
25 }
26 --top;
27 break;
28 case '+':
29 case '-':
30 while (top > 0 && stack[top - 1] != '(')
31 {
32 postfix[j++] = stack[--top];
33 }
34 stack[top++] = ch;
35 break;
36 case '*':
37 case '/':
38 while (top > 0 && (stack[top - 1] == '*' || stack[top - 1] == '/'))
39 {
40 postfix[j++] = stack[--top];
41 }
42 stack[top++] = ch;
43 break;
44 case ' ':
45 break;
46 default:
47 postfix[j++] = ch;
48 }
49 ch = infix[i++];
50 }
51 while (top > 0)
52 {
53 postfix[j++] = stack[--top];
54 }
55 postfix[j++] = '\0';
56 return postfix;
57 }
58
59 int main()
60 {
61 char infix[MAX];
62 char stack[MAX];
63 char postfix[MAX];
64
65 scanf("%s", infix);
66 infixToPostfix(postfix, infix);
67 printf("%s\n", infix);
68 printf("%s\n", postfix);
69 return 0;
70 }
posted @
2011-06-30 20:36 unixfy 閱讀(154) |
評論 (0) |
編輯 收藏表達式的運算
總共分兩個步驟
·中綴表達式轉換成后綴表達式
·后綴表達式的計算
中綴表達式轉換成后綴表達式：
掃描一遍中綴表達式
操作符棧
左括號和右括號的特殊性
運算符的優先級
后綴表達式的計算：
掃描一遍后綴表達式
操作數棧
當前操作符，操作數棧出棧計算，注意雙目運算符的左右順序
表達式運算的整個過程，利用了兩個棧
·操作符棧
·操作數棧
分別應用于第一和第二步驟中。
在做中綴表達式轉換成后綴表達式的過程中需要注意左括號和右括號的入棧出棧，其他操作符相對左括號和右括號的入棧和出棧。注意左括號的棧內優先級與棧外優先級的區別。
實現：
1 //
2 // 表達式運算
3 // Mark
4 // email: goonyangxiaofang AT 163.com
5 // QQ : 591247876
6 // 2011.6.29
7 // ( ( 1 + 2 ) * 3 + ( 1 + 10 ) ) / 2
8 // ???
9 //
10
11 #include <iostream>
12 #include <string>
13 #include <vector>
14 #include <stack>
15 #include <map>
16 #include <cstdlib>
17 using namespace std;
18
19 map<string, int> operatorPriors;
20
21 void getInfix(vector<string>& infix)
22 {
23 infix.clear();
24 string tmp;
25 while (cin >> tmp)
26 {
27 infix.push_back(tmp);
28 }
29 }
30
31 void init()
32 {
33 operatorPriors["+"] = 10;
34 operatorPriors["-"] = 10;
35 operatorPriors["*"] = 20;
36 operatorPriors["/"] = 20;
37 operatorPriors["%"] = 20;
38 operatorPriors["("] = 30;
39 operatorPriors[")"] = 0;
40 }
41
42 bool prior(const string& op1, const string& op2)
43 {
44 return operatorPriors[op1] > operatorPriors[op2];
45 }
46
47 bool isOperator(const string& s)
48 {
49 return operatorPriors.find(s) != operatorPriors.end();
50 }
51
52 void print(stack<string> operators)
53 {
54 while (!operators.empty())
55 {
56 cout << operators.top() << ' ';
57 operators.pop();
58 }
59 cout << endl;
60 }
61
62 const vector<string>& infixToPostfix(vector<string>& postfix, const vector<string>& infix)
63 {
64 postfix.clear();
65 stack<string> operators;
66 for (vector<string>::size_type i = 0; i != infix.size(); ++i)
67 {
68 if (isOperator(infix[i]))
69 {
70 if (operators.empty())
71 {
72 operators.push(infix[i]);
73 }
74 else if (operators.top() == "(" && infix[i] != ")" || prior(infix[i], operators.top()))
75 {
76 operators.push(infix[i]);
77 }
78 else
79 {
80 if (infix[i] == ")")
81 {
82 while (operators.top() != "(")
83 {
84 postfix.push_back(operators.top());
85 operators.pop();
86 }
87 operators.pop();
88 }
89 else
90 {
91 postfix.push_back(operators.top());
92 operators.pop();
93 while (!operators.empty() && !prior(infix[i], operators.top()) && operators.top() != "(")
94 {
95 postfix.push_back(operators.top());
96 operators.pop();
97 }
98
99 operators.push(infix[i]);
100 }
101 }
102 }
103 else
104 {
105 postfix.push_back(infix[i]);
106 }
107 }
108 while (!operators.empty())
109 {
110 postfix.push_back(operators.top());
111 operators.pop();
112 }
113 return postfix;
114 }
115
116 double stringToDouble(const string& s)
117 {
118 return (atof(s.c_str()));
119 }
120
121 double evalPost(const vector<string>& post)
122 {
123 stack<double> operands;
124 int a, b;
125 for (vector<string>::size_type i = 0; i != post.size(); ++i)
126 {
127 if (post[i] == "+")
128 {
129 b = operands.top();
130 operands.pop();
131 a = operands.top();
132 operands.pop();
133 operands.push(a + b);
134 }
135 else if (post[i] == "-")
136 {
137 b = operands.top();
138 operands.pop();
139 a = operands.top();
140 operands.pop();
141 operands.push(a - b);
142 }
143 else if (post[i] == "*")
144 {
145 b = operands.top();
146 operands.pop();
147 a = operands.top();
148 operands.pop();
149 operands.push(a * b);
150 }
151 else if (post[i] == "/")
152 {
153 b = operands.top();
154 operands.pop();
155 a = operands.top();
156 operands.pop();
157 operands.push(a / b);
158 }
159 else if (post[i] == "%")
160 {
161 b = operands.top();
162 operands.pop();
163 a =operands.top();
164 operands.pop();
165 operands.push(a - b);
166 }
167 else
168 {
169 // stringstream ss;
170 // ss << post[i];
171 // ss >> a;
172 operands.push(stringToDouble(post[i]));
173 }
174 }
175 return operands.top();
176 }
177
178 int main()
179 {
180 init();
181 vector<string> infix;
182 vector<string> postfix;
183 getInfix(infix);
184 infixToPostfix(postfix, infix);
185 for (vector<string>::size_type i = 0; i != postfix.size(); ++i)
186 {
187 cout << postfix[i] << ' ';
188 }
189 cout << endl;
190 cout << evalPost(postfix) << endl;
191 return 0;
192 }
posted @
2011-06-29 01:58 unixfy 閱讀(169) |
評論 (0) |
編輯 收藏