面试题 100 —— 5 查找 Top K
这里的做法是利用一个堆，用这个堆作为 K 个元素的输出容器，堆的特点是可以以 O(1) 的效率去堆中最大/小的元素。
正式利用了这一点，这种方法的时间复杂度为 O(NlogK)
查找最小的 K 个数
利用最大堆
思路时，开始的时候堆为空，堆中元素个数还不足 K 个，所以遍历的当前元素直接加入到堆中
当堆中元素等于 K 的时候，检查当前元素与堆中最大元素的大小关系，若大于最大元素则忽略，否则将堆中最大元素删除，并将当前元素添加到堆中。
整个过程，遍历一遍集合，每次针对当前元素需要对堆进行调整，总的时间复杂度为 O(NlogK)
http://www.cppblog.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 阅读(282) |
评论 (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 阅读(190) |
评论 (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 阅读(138) |
评论 (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 阅读(250) |
评论 (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 阅读(510) |
评论 (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://www.cppblog.com/momoxiao/archive/2010/06/26/118758.html
posted @
2011-07-11 11:22 unixfy 阅读(422) |
评论 (1) |
编辑 收藏最短摘要的生成
这个问题在《编程之美》中提到过。前几天百度三面的时候也问到了这个问题，当时没有答上来。从新翻阅了一下《编程之美》。
直观的解决方案是：
从文档第一个词开始遍历，寻找后面的词是否与关键词数组匹配
然后从文档第二个、第三个 ... 一直到最后一个词遍历
这个过程要记录最短文摘的信息。
这个时间复杂度是 O(N ^ 2 * M)
N 是文档的长度
M 是关键词数组的大小
改进的方法是：
对于求的的一个文摘，记录第一次出现关键词的位置，然后直接移动到该关键词，然后右边的边界再向后移动。
这个时间复杂度是 O(N)
这种方法也就是说维持了一个摘要滑动窗口，一遍扫描文档即可得到相应的最短摘要。
摘要中的关键词可以用一个队列来存储，因为摘要滑动窗口的左边界和右边界都是要从左到右移动的。所以队列正好适用。另外还应该维持一个对应文摘滑动窗口中的关键词出现的次数表。在做左右边界移动时需要考量这个次数表所提供的信息。
posted @
2011-07-03 20:34 unixfy 阅读(1073) |
评论 (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://www.cppblog.com/life02/archive/2009/10/17/98851.html
posted @
2011-07-02 13:51 unixfy 阅读(256) |
评论 (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 阅读(129) |
评论 (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 阅读(128) |
评论 (0) |
编辑 收藏