九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

黑客调试技术揭秘(Hacker Debugging Uncovered) 学习(1) 最简单的密码保护破解


黑客调试技术揭秘(Hacker Debugging Uncovered 学习(1 最简单的密码保护破解

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

源代码

#include "stdafx.h"

#include <iostream>

#include <cstring>

using namespace std;

#define LEGAL_PSW "my.good.password"

 

int main(int argc, char* argv[])

{

    char lszCharPsw[100]
= {0};

 

    cout << "Crackme 00h/nenter passwd:";

    cin >>lszCharPsw;

    if(strcmp(LEGAL_PSW, lszCharPsw))

    {

       cout << "wrong password/n";

    }

    else

    {

       cout << "password ok/nhello, legal user!/n";

    }

 

 

 

    return 0;

}

 

我是在VS2005 SP1 Release下编译的,以下的汇编代码都是这个编译器生成的。

对于这么简单的程序,只能是用来熟悉工具了。。。。怎么说以前也是玩过一下的,呵呵。

按以前的传统步骤,先用PEID打开文件看看,哦,VS2005-2008编译的,没有加壳。(纯粹为了说明步骤.....)运行程序输出看结果,wrong password,ok就找这个字符串,用Ollydbg打开,查找参考字符串,就列出了所有的字符串了,连答案都已经出来了,假设此时不知道答案,双击定位到wrong password所在的位置,


00401063     /74 0D         JE     
SHORT JustForH.00401072

00401065  |. |A1 60204000   MOV    
EAX, DWORD PTR [<&MSVCP80.std::c>

0040106A  |. |68 64214000   PUSH   
JustForH.00402164               
;  ASCII "wrong
password",LF

0040106F  |. |50            PUSH    EAX

00401070  |. |EB 0C         JMP    
SHORT JustForH.0040107E

00401072  |> /8B0D 60204000 MOV     ECX, DWORD PTR
[<&MSVCP80.std::c>; 
MSVCP80.std::cout

00401078  |.  68
74214000   PUSH    JustForH.00402174                ;  ASCII "password ok",LF,"hello,
legal user!",LF

 

这个时候,谁都应该知道,这个第一行的JE就是判断完结果的跳转了,判断正确的话就输出了ASCII "password
ok",LF,"hello, legal user!",LF
,不然继续执行,输出ASCII "wrong
password",LF
,该怎么改也很明了了。。。。。

晕,用OllyDbg就达不到目的了。现在是来学别的工具的,按照书中的思路来走吧。

使用IDA Pro,直接载入文件,分析完毕,按书中提示,打开数据段(data),可是这个程序似乎不和书中一样,相关数据存储在(.rdata)中,如下所示,而不是.data中,因为目前对于PE文件格式还不是太熟悉(熟悉PE格式就是我下一步需要做的工作)还不知道出现与书中不一致情况的原因。

.rdata:0040211C
; struct _EXCEPTION_POINTERS ExceptionInfo

.rdata:0040211C
ExceptionInfo   _EXCEPTION_POINTERS
<offset dword_403040, offset dword_403098>

.rdata:0040211C                                         ; DATA
XREF: sub_4013A2+390o

.rdata:00402124
aBadAllocation  db 'bad
allocation',0   ; DATA XREF:
.data:00403018o

.rdata:00402133                 align 4

.rdata:00402134
aCrackme00hEnte db 'Crackme 00h',0Ah    ;
DATA XREF: sub_401000+32o

.rdata:00402134                 db 'enter passwd:',0

.rdata:0040214E                 align 10h

.rdata:00402150
aMy_good_passwo db 'my.good.password',0 ; DATA XREF: sub_401000+55o

.rdata:00402161                 align 4

.rdata:00402164
aWrongPassword  db 'wrong password',0Ah,0
; DATA XREF: sub_401000+6Ao

.rdata:00402174
aPasswordOkHell db 'password ok',0Ah    ;
DATA XREF: sub_401000+78o

 

OK,还是找到了wrong password,然后用IDA Pro的交叉引用,OK一样搞定了,一样可以找到wrong number被引用的地址,看到相关的源代码(其实应该说是反汇编代码):

.text:00401063                 jz      short loc_401072

.text:00401065                 mov     eax,
ds:?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ;
std::basic_ostream<char,std::char_traits<char>> std::cout

.text:0040106A                 push    offset aWrongPassword ; "wrong
password/n"

.text:0040106F                 push    eax

.text:00401070                 jmp     short loc_40107E

.text:00401072
;
哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪哪?

.text:00401072

.text:00401072
loc_401072:                             ;
CODE XREF: sub_401000+63j

.text:00401072                 mov     ecx,
ds:?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ;
std::basic_ostream<char,std::char_traits<char>> std::cout

.text:00401078                 push    offset aPasswordOkHell ; "password
ok/nhello, legal user!/n"

.text:0040107D                 push    ecx

 

一样还是傻子都能看出第一行在干什么,问题基本能够解决了。

其实不按书中所做,IDA Pro中有个string window,其中已经有所有的字符串了,这点和OllyDbg的查找有所引用字符串功能一样。相对而言,两个工具都很好用。但是IDA Pro生成的反汇编代码可读性相对还是更强一些,可能毕竟是用于静态分析用途的,所以对于代码有可能可进行的跳转操作,也是很方便:)

但是,想起谁说的来者OllyDbg就像是SoftIce + IDA Pro。。。。。呵呵,OllyDbg的确简单易用,我可以证明,但是是否是和SoftIce+IDA Pro这样强大嘛,还有待我继续学习,以了解真实情况。

 

继续:

Kris
Kasperasky
说上面这些都是工具的功能,和我们自己没有关系。。。。的确是,虽然我不是黑客,但是也继续下去了。。。。

HIEW32。。。。。。。。呵呵,原以为仅仅是一个16进制的编辑器,所以我还想假如不好用我就继续用我的WinHEX(这个可爱的家伙伴随着我很长很长的岁月了,虽然很多人喜欢用UE来做16进制编辑器,但是我在研究一个文件打包格式的时候才真的体会到,UEWinHex的差距,WinHex就是为编辑16进制为生的。。。。。。参看我以前贴的惨烈的工作环境的图,那就是WinHex伴随我工作的场景。

HIEW32是个命令行工具,打开文件后,一堆乱码。。。。书中实在没有详细讲解怎么用,只好自己研究研究啦,Linux下那么多命令行的工具都不在话下,不怕这一个。和许多有简陋图形界面的命令行工具一样,操作命令都写在最下面,如图,


但是你在尝试直接按数字没有用后,自然就是按F系列了,按F1可以看使用帮助,内容还真不少。。。。。。。。仔细研究一下吧。继续说。

先按F4,选择HEX模式,查找wrong number ASCII值,查到的地址,在我的机器中是。这里用F1中看到的有趣功能Atl-P,抓屏:)

.004020A0:  3C 25 00 00-28 25 00 00-12 25 00 00-04 25 00
00  <% 
(%   %   %   

.004020B0:  F8 24 00 00-EC 24 00 00-E4 24 00 00-D6 24 00
00  ? 
?  ?  ?   

.004020C0:  CE 24 00 00-C4 24 00 00-B4 24 00 00-A6 24 00
00  ? 
?  ?  ?   

.004020D0:  90 24 00 00-2A 2A 00 00-40 2A 00 00-00 00 00
00  ? 
**  @*       

.004020E0:  00 00 00 00-B1 13 40 00-00 00 00 00-00 00 00
00      ?@          

.004020F0:  72 15 40 00-9F 17 40 00-00 00 00 00-00 00 00
00  r @ ?@          

.00402100:  00 00 00 00-BD 1B 62 49-00 00 00 00-02 00 00
00      ?bI         

.00402110:  67 00 00 00-E8 21 00 00-E8 11 00 00-40 30 40
00  g  
?  ?  @0@  

.00402120:  98 30 40 00-62 61 64 20-61 6C 6C 6F-63 61 74
69  ?@ bad allocati 

.00402130:  6F 6E 00 00-43 72 61 63-6B 6D 65 20-30 30 68
0A  on 
Crackme 00h  

.00402140:  65 6E 74 65-72 20 70 61-73 73 77 64-3A 00 00
00  enter passwd:    

.00402150:  6D 79 2E 67-6F 6F 64 2E-70 61 73 73-77 6F 72
64  my.good.password 

.00402160:  00 00 00 00-77 72 6F 6E-67 20 70 61-73 73 77
6F      wrong passwo 

.00402170:  72 64 0A 00-70 61 73 73-77 6F 72 64-20 6F 6B
0A  rd 
password ok  

.00402180:  68 65 6C 6C-6F 2C 20 6C-65 67 61 6C-20 75 73
65  hello, legal use 

.00402190:  72 21 0A 00-70 61 75 73-65 00 00 00-00 00 00
00  r! 
pause        

.004021A0:  48 00 00 00-00 00 00 00-00 00 00 00-00 00 00
00  H                

.004021B0:  00 00 00 00-00 00 00 00-00 00 00 00-00 00 00
00                   

.004021C0:  00 00 00 00-00 00 00 00-00 00 00 00-00 00 00
00                   

.004021D0:  00 00 00 00-00 00 00 00-00 00 00 00-00 30 40
00               0@  

.004021E0:  50 22 40 00-03 00 00 00-52 53 44 53-0D F5 61
EF  P"@     RSDS
?

.004021F0:  22 6B C6 4D-9D 15 B2 31-EB B1 74 CB-02 00 00
00  "k
??t?    

 

记下地址00402160,按F5 0 enter跳转到文件头,再搜寻哪个地方使用到了这个字符串的地址,搜寻的时候因为0x86是小头机,搜寻60 21 40 00,搜到后,按F4 切入Decode模式,这是HIEWWinHex强大的地方了。。。。WinHex不带反汇编功能。。。。不过我奇怪的是。。作者最终还是用到了工具来反汇编,然后理解。。。仅仅因为自己多搜寻了两下地址。。。这就体现了技术了?-_-!

 

.00401047:
50                           push        eax                       

.00401048:
FF1558204000                 call        ??$?5DU?$char_traits@D@std@

.0040104E:
83C410                       add         esp,010 ;" "              

.00401051:
8D7C2408                     lea         edi,[esp][08]             

.00401055:
BE50214000                   mov         esi,000402150 ;'my.good.pas

.0040105A:
B911000000                   mov         ecx,000000011  --- 
(2)   

.0040105F:
33D2                         xor         edx,edx                   

.00401061:
F3A6                         repe        cmpsb                     

.00401063:
740D                         je         .000401072  --- 
(3)       

.00401065:
A160204000                   mov         eax,std::cout ;MSVCP80    

.0040106A: 6864214000                   push        000402164  --- 
(4)       

.0040106F:
50                           push        eax                       

.00401070:
EB0C                         jmps       .00040107E  --- 
(5)       

.00401072:
8B0D60204000                 mov         ecx,std::cout ;MSVCP80    

.00401078:
6874214000                   push        000402174  --- 
(6)       

.0040107D:
51                           push        ecx                       

.0040107E:
E85D010000                   call       .0004011E0  --- 
(7)       

.00401083:
83C408                       add         esp,008 ;" "              

.00401086:
6894214000                   push        000402194 ;'pause'        

.0040108B:
FF15D0204000                 call        system ;MSVCR80           

.00401091:
8B4C2478                     mov         ecx,[esp][78]             

.00401095:
83C404                       add         esp,004 ;" "              

.00401098:
5F                           pop         edi                       

 

粗体显示的就是我们搜寻到的那一行,到了这里,看看前两行,什么都知道了。

这里说下在HIEW中的改法,按F3进入编辑模式,直接将00401063这行改为第二排那样,按F9 Update,再按F10退出,再运行,就发现怎么都是正确的了。

.00401063:
740D                         je         .000401072  --- 
(3)

.00401063:
EB0D                         jmps       .000401072  --- 
(3)  

 

这里的修改有个不方便的地方就是,假如在编辑模式中直接按EnterF2进入Asm输入方式的修改,会破坏整个程序,因为HIEW不会将jmps 000401072改为near的相对偏移跳转方式的汇编代码(即EB0D),而是直接将jmps 000401072翻译为绝对地址的跳转方式,因为代码的数量远远的大于了原来的两个字节(光是地址就需要4个),所以导致程序破坏了。这里要说明的是,OllyDbg就要强大的多,它会进行这样适当的转换,并且还可以自动的在你将长代码改为短代码时为你用NOP填充。其实最简单的办法就是找到原有代码的合适位置,然后修改成代码长度一样的代码,这在插入代码很短的时候(比如一个简单的jmp)时很有用。在书中仅仅描述了怎么在原地修改的办法。其实常用的办法还包括一种简单的代码注入方式,即将某条指令换成跳转语句,跳转到某个空地方,将我们要执行的代码放在那里,以前我甚至试过动态调试的时候,直接输入指令执行:)这样可是很好很强大的啊。

原地修改嘛,起码得给自己的语句腾出位置,但是不伤害其他的原有语句。比如改成下面这样:

0040105F   . /EB 11         JMP    
SHORT JustForH.00401072

这样就绕过了检测了,一样可以达到目的。。。。太晚了,今天就到这里吧,其实好像除了IDA ProHIEW最基本的用法,什么都没有学会。

 

 

 

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

阅读全文....

工作方向又换了,开始研究反外挂技术

以前自己是非常羡慕这样一群人的,每天对着汇编代码,任何软件无论怎么加壳,怎么加密,在他们看来都是源码。
呵呵,后来玩游戏的时候,也慢慢接触了一些东西,从DOS时代修改那些老RPG游戏的PCTools到FPE,到后来用的GE及与NP做斗争等等,往往在根据以往的教程,在新版的游戏中通过了游戏中的碰撞检测(达到无敌),极端的兴奋,虽然那时那个游戏已经是外挂漫天了,但是我往往可以在新版更新,外挂还没有发布之前就享受到外挂(乐趣?)呵呵。
以至于听说我们公司也要做这样的东西后(当然是反外挂了),我是非常的有兴趣。
虽然经过了这么久的工作,一些事情也看开了,而且我有了个很重要的认识,我是程序员,不是黑客。知道破解这东西是无止境的,所以反破解的事情也不会有止境,而且,这些对于你真正设计代码,写代码的帮助往往没有那么大,不说没有帮助吧,但是从消耗的时间到获得的帮助来说,肯定比老老实实多写点有意思的代码少的多吧。但是,趁这个机会,好好的把原来学了又忘忘了又学的asm好好巩固一下,这是有百利而无一害的事情。

而且,兴趣嘛,曾经这样想过,假如公司让我干反外挂的事情,我将把我的业余时间也拿出来工作。(看看我的博客,就知道其实我的业余时间还是干了很多事情的),所以,我业余也会研究反外挂技术了,初期阶段么,自然是以熟悉工具什么的为主了,以前用了OllyDbg,但是最近看了书以后,发现SoftIce才是王道。。。。。毕竟ring3和ring0的可以做的事情还是不一样的。
慢慢来吧,可怜我的数据结构学习又要卡住了,这点才是最郁闷的。

阅读全文....

VMWare虚拟机安装,SoftIce在虚拟机中的安装


VMWare虚拟机安装,SoftIce在虚拟机中的安装



write by 九天雁翎(JTianLing) -- www.jtianling.com

先来个开胃菜,为了安全起见(太多的破解工具都感觉不一定可靠,主要是来源。。。。)
还是用虚拟机比较安全,假如不想重复的开机关机及重装系统的话。
    

VMWare算是比较好的虚拟机了,虚拟机的领军人物。
我 安装的是虚拟先锋的绿色版,解压,点击绿化批处理文件就可以完成安装。然后新建一个虚拟机,配置一下内存,硬盘空间,像普通电脑一样安装系统就完了,
安装完不要忘了克隆一个来备份。安装系统的时候,VMWare有个好用的设置是从镜像(ISO等)来安装,这个只要在光驱的设置中选择就好了,非常的方 便。

要想SoftIceVMWare中正常使用,花费的功夫就需要多一点了。
1.
首先的安装VMWare Tools,这在客户端虚拟机启动的时候,选择VMWare的虚拟机菜单,选择安装VMWare Tools就可以安装了。(碰到过点击没有反应的情况,这个时候你可以选择在Host载入VMWare安装盘下的windows.iso镜像,那么也就可
以在客户端虚拟机安装了,这是windows版的VMWare Tools,不过要说明的是,不要在你虚拟出来的机器上装DaeMon,就我实验,那样会和SoftIce冲突,据说3.9以下版本不会,你可以去试 试)。
2.
安装SoftIce或者Driver Studio,反正都包含有SoftIce,选择显卡的时候,配置不需要改动,只是点击Test试试,只要第一步没有问题,这时候test应该也可以成功,没有第一步的话必然失败。
3.
关闭虚拟机,打开虚拟机的配置文件(你新建的虚拟机所在的目录),VMX后缀的文件,在最后添加
vmmouse.present = "FALSE"
svga.maxFullscreenRefreshTick = "5"
两行,再重新启动,选择开始菜单中SoftIceStart
SoftIce
,然后就可以按CTRL-D看看是否能够正常运行了,应该没有问题。

 

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

阅读全文....

堆栈的简单lua实现


堆栈的简单lua实现

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 1 #!/usr/bin/env lua
 2 require "CList"
 3
 4 CStack = CList:New()
 5
 6 function CStack:Top()
 7     return self:End():MovePrev().pos.data
 8 end
 9
10 function CStack:Push(a)
11     self:PushBack(a)
12 end
13
14 function CStack:Pop()
15     self:PopBack()
16 end
17
18 function CStack:Size()
19     return CList.Size(self)
20 end
21
22 -- Test CStact
23 s = CStack:New()
24 s:Push(10)
25 print(s:Top())
26 s:Push(20)
27 print(s:Top())
28 s:Push(30)
29 print(s:Top())
30 s:Pop()
31 print(s:Top())
32 print(s:Size())
33
34
35
36
37

 

CList的是一个我用链表实现的表(仿照C++list 实现

具体实现见

http://www.jtianling.com/archive/2008/12/25/3606972.aspx

其实到了这个层次的lua语法(用一个类去实现另一个类),我已经不是太了解了,Programming in lua中也没有出现类似的语法,只简单的提到了怎么去New,书中是用这种方式去实现继承的。第19行的语法纯粹是自己摸索出来的,一开始用self:Size(),结果并没有从CList中去找,而是陷入了纯粹的递推自身调用。

 

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

阅读全文....

对Linker.Lin的 《[备忘]Lua的local是定义不是声明!》的研究


Linker.Lin [备忘]Lualocal是定义不是声明!》的研究

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

因为这样的特性实在是太奇怪了,所以不得不好好研究一下。

原文见http://blog.csdn.net/linkerlin/archive/2008/12/25/3603897.aspx

由于很短,我贴过来,顺便给他的代码上个色

test1:

1 g='hi~'
2 local g='hello!'
3 for i=1,2 do
4
    local g=g..'1'
5 print(g)
6 end

输出:

hello!1

hello!1

 

他的结论很明显了,题目就是了。先推断一下他的理解(假如不对请告诉我啊:)

因为上述程序输出

hello!1

hello!1

而下面这种仅仅去掉了local的程序

test2:

1 g='hi~'
2 local g='hello!'
3 for i=1,2 do
4
    g=g..'1'
5 print(g)
6 end

 

输出的是

hello!1

hello!11

 

注意区别,没有local的时候,g相当于直接在原有的基础上加了1,而加了local的时候是两次重新的定义,都是hello!1。自此,Linker.Lin得出了结论,“Lualocal是定义不是声明!”。呵呵,好像一切都比较符合逻辑,不知道Linker.Lin是不是这样理解的。

 

其实,我的理解是,虽然这一次local的声明导致g变成定义,但是说local就是定义。。。。好像很奇怪。。。。。

test3:

1 g='hi~'
2 local g='hello!'
3 for i=1,2 do
4     x=g..'1'
5 print(x)
6 end

 

一样是可以得出

hello!1

hello!1

的和test1一致的输出的,这里x没有local,也是定义

test2:得出的那样的结果原因在于,由于for外部已经有个变量g了,所以在用

g=g..'1'

的语句时,相当于使用了外部的g,即将for前的local gg改变了,第二次循环的时候,还是用外部的g,此时的g已经被改变了,所以相当于在hello1后再加了个1.

test1:中用了local,其实是声明此处的g变量为局部变量,而局部没有g变量,按照lua的规则是自动定义出g变量来进行操作的,此时for循环内局部的g赋值为hello1,当此次循环结束时,局部的变量g自动销毁(作用域结束了),第二次循环开始的时候,重新定义了新的局部变量g,所以两次都是hello1

这里多给出几个例子:

test4:

1 g='hi~'
2 local g='hello!'
3 for i=1,2 do
4     g = g .. '1'
5     print(g)
6 end
7 print(g)

输出:

hello!1

hello!11

hello!11

证明内部变量g的使用,实际是用了外部的变量g

最后来个复杂点的例子:

test5:

 1 g='hi~'
 2 local g='hello!'
 3 for i=1,2 do
 4     print(x)
 5     x = x and x .. '1' or g .. '1'
 6     print(x)
 7     local x = x .. '1'
 8     print(x)
 9     local x = x .. '1'
10     print(x)
11 end
12 print(x)

输出

nil                               -- 第一次进入循环输出时,xnil

hello!1                               -- 因为xnil,所以第5行第一次运行后,xg..’1’,此处x明显也是定义

hello!11                      -- local x = hello!1 .. ‘1’
还没有什么好奇怪的

hello!1                        -- 第二次进入循环,此时x已经有值了,并且是hello!1,那么表示此值是前一个没有加local定义的x,因为local x应该起码是hello!11 

hello!11                      -- 第二次第五行后此时非localx也变成了hello!11

hello!111                    -- 此时local x又重新定义一次,所以等于hello!11 .. ‘1’

hello!11                      -- localx有超出for的作用域

 

其实,这仅仅是个作用域的问题,lua中有起码有两个作用域,全局的,局部的,for构成一个Block(),构成一个局部的概念,local的变量,作用域就在此局部内直到此局部范围结束。一个循环结束后,也算是一次局部范围的结束。于是local的变量销毁了。

形成了上述的看似奇怪的输出结果,其实本质上是作用域的特点,仅仅是三个语言特点的叠加效果。

1.     
lua作为动态脚本语言有的自动定义变量特性。

2.     
几乎所有的语言的(起码我知道的那么几种是)都有局部掩盖全局的概念,这是为了更好的局部化,不因为全局的东西影响局部。

3.     
lua比较少见的默认全局特性,这点的确少见(bash也是),因为这是和前一点的好处相违背的,可能属于老的脚本语言的遗留特性。

特性1自动定义特性的结果就是在一个作用域中发现使用一个没有定义的变量(上述例子中为xg)就自动定义一个来使用,而不需要像静态语言(如C/C++)中一样先确定的定义,再使用。特性2局部掩盖导致在用local声明使用某个局部变量时,lua发现局部没有此变量,就自动定义了一个。并且此local变量的作用域内,再次使用此变量名,优先使用局部的,比如test5810行输出的就是local变量的值,而不是前一个全局的x.

默认全局不影响Linker.Lin的测试,但是影响了最后一个测试的结果。

总而言之,Linker.Lin能够得出的结论都是变量的作用域问题,就算是其他语言也是类似的:

为了对比,看一个C++程序(不调试了啊)

string
str = “Hello!”;

for (int
i = 0; i  < 2; ++i)

{

       string str = str + “1”;

       cout <<string;

}

cout
<<string;

 

只是,在C++中,局部的概念是默认的,没有local,一样定义。

 

但是,呵呵,好东西都是留到最后嘛,(不要怪我前面废话那么多,认清楚问题嘛,靠C++吃饭的我。。。有个特点就是喜欢知其然,并知其所以然,所以解释起来都是一大堆的。。。。)

for
i=1,2 do

local g
= ‘1’

local g
= ‘2’

end

时,第二个g是复用了第一个g呢?还是重新定义了一个新的变量g?这才是问题的关键。最简单的办法自然是看两个g的地址是否一样。。。。不过好像没有把办法(还是我不知道??)在lua中获取一个普通变量的地址啊。

我尝试这样做

 1 g
= {}
 2 for i=1,2 do
 3     io.write("global
g:"
)
 4     print(g)
 5     local g = {}
 6     io.write("first
local g:"
)
 7     print(g)
 8     local g = {} 
 9     io.write("second
local g:"
)
10     print(g)
11 end
12 print(g)

毕竟table是可以看到地址的。。。。结果输出的地址是不一样的。我可以确定结论了吗?真是这样也许还草率了一点。这点也许还不一定能够说明问题,因为每次lua都会创建{},两次的{}可以都是创建出来的,g不过就是对于{}的一个引用,两次输出不同的地址也许仅仅代表了两个不同的{}的地址而已,还是不能说明g的地址。

从普通代码没有办法获得结果,那么借助于其他办法罗,我首先想到的就是调试,没有问题,试试:

 1 #!/usr/bin/env lua
 2
 3 g = '1'
 4 for i=1,2 do
 5     g = g .. '2' 
 6     local g = '3'
 7     local g = g .. '4'
 8     g = g .. '5'
 9     local i = 1
10     while true do
11         local name,value = debug.getlocal(1,i)
12         if not name
then 
13             break 
14         end
15
16         print(name, value)
17         i
= i + 1
18     end
19 end

输出的结果:

(for
index)     1

(for
limit)     2

(for
step)      1

i       1

g       3

g       345

i       7

(for
index)     2

(for
limit)     2

(for
step)      1

i       2

g       3

g       345

i       7

 

5行对g的使用,但是没有输出证明debug.getlocal并不是对每个在局部使用的变量都获取,仅仅获取在局部分配的变量,那么一次g 3,一次g 345的出现就很能说明问题了,g 34的定义也没有出现,说明getlocal仅仅获取的是分配变量的最后保留值,作为变量g,最后的值有2个,一个3,一个345,说明的确是一个local定义了一个变量。。。。。。只有到这个时候,我才能得出Linker.Lin的结论。

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

阅读全文....

数据结构 链表的lua实现 仿照C++中list 实现

 

数据结构 链表的lua实现 仿照C++list 实现

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

vector我就没有用lua实现了,实现个list就很别扭了。事实上太仿照C++标准库的list了,所以可能没有很好的发挥lua的特点,有点要说的就是,luatable的赋值都是引用赋值的浅拷贝,这点在实现list的时候发挥了关键作用,不然没有指针的lua要实现一个列表都成为不可能了:)

程序最后还附加了一个符合lua迭代器特点的迭代器,不然老是用CListIterator的话,可能都会怀疑自己用的还是不是lua了,呵呵

 这里想提出的一点就是lua中实在是没有一个可用的debug工具,注意我的措辞,是连一个可用的都没有,更别提好用的了。相对而言C++VS+gdb,pythonpydbbashbashdb,lua什么都没有!lua for windows的那个scite别提多不好用了,clidebug,xdblua, RemDebug等等我都用过,甚至官网提到的几个IDE我都试用了一下,通通的不能用,可能是因为lua升级了的原因(记得scite在原来是可用的),郁闷死我了。作为一个两百多行的list代码,没有一个可用的调试工具,简直就是噩梦(也许没有那么夸张,但是的确浪费了我很多本来简单调试就可以发下你的问题),唉。。。。。在没有好用的lua调试工具之前,我甚至都有点不想给自己找罪受了。再也不写太多的lua代码了。最多在小程序中用printassert勉强写写吧。其实感觉lua本身对于调试的支持是很到位的了,为什么却没有好用的工具呢?唉。。。。。。。。。。这就是普及的好处了。。。。。真有时间,哥们自己DIY一个用用算了。

-----在对lua的调试工具不再抱希望的时候,调整了一下lua的PATH设置,随便折腾了一下scite,结果又可以正常调试了,faint.............有的时候就是这么莫名奇妙,我折腾了3天(准确的是3天的晚上),试了n种工具,结果都有问题,结果今天莫名奇妙就好了,谁说的来着,你编的认为已经没有bug的软件总会在某一天莫名崩溃。。。。这一点在工作以来我是深有体会了,问题是,某个有bug,已经不能正常运行的软件怎么在某一天莫名的好了呢?。。。。呵呵。

总之,还是对lua的调试工具不满,起码,没有能够让我能用putty挂在linux下好好调试的工具:)总不能每次在那边写完都考回来在windows下调试吧?。。。(现在好像也只能这样了)

 

  1 #!/usr/bin/env lua
  2
  3 --
require "std"

  4
  5 --
Node prototype

  6 CNode = {}
  7 function CNode:New(data,
prev, next)
  8     local o = {}
  9     o.data
= data
 10     o.prev =
prev
 11     o.next = next
 12     o.type = "CNode"
 13     setmetatable(o, self)
 14     self.__index
= self
 15     return o
 16 end
 17
 18 --
iterator of list prototype like in C++

 19 CListIterator = {}
 20 function CListIterator:New(a)
 21     assert(a ~= nil and 
 22     type(a) == "table" and 
 23     a.type ~= nil and
 24     ((a.type == "CList")
or (a.type ==
"CNode")),
 25     "Argument to new a CListIterator must be a CList
object or a CNode object"
)
 26     
 27     local o = {}
 28     -- give it a type name
 29     o.type = "CListIterator"
 30
 31     -- if a is a CList object then create a begin iterator for
the object

 32     -- if a is a CNode object then return a iterator point to
the node

 33     if a.type ==
"CList" then
 34         o.pos
= a.head.next
 35     elseif a.type ==
"CNode" then
 36         o.pos
= a
 37     end
 38
 39     setmetatable(o, self)
 40     self.__index
= self
 41     return o
 42 end
 43
 44 function CListIterator:IsEnd()
 45     return not self.pos.data
 46 end
 47
 48 function CListIterator:Cur()
 49     return self.pos
 50 end
 51
 52 function CListIterator:MoveNext()
 53     self.pos =
self.pos.next
 54     return self
 55 end
 56
 57 function CListIterator:MovePrev()
 58     self.pos =
self.pos.prev
 59     return self
 60 end
 61
 62 -- List
prototype

 63 CList = {}
 64 function CList:CreateIterator()
 65     return CListIterator:New(self)
 66 end
 67
 68 function CList:New()
 69     local o = {}
 70     o.head =
CNode:New()
 71     o.head.prev
= o.head
 72     o.head.next = o.head
 73
 74     -- give it a type def
 75     o.type = "CList"
 76     setmetatable(o, self)
 77     self.__index
= self
 78     return o
 79 end
 80
 81 function CList:Insert(it,
data)
 82     assert(it ~= nil, "Must pointer where to Insert")
 83     assert(type(it) == "table", "Fisrt
Argument must be a CListIterator(now it even not a table)"
)
 84     assert(type ~= nil, "Fisrt
Argument must be a CListIterator(now it.type == nil)"
)
 85     assert(it.type ==
"CListIterator", "Fisrt Argument must be a CListIterator")
 86
 87     local iter = CListIterator:New(self)
 88     local node = CNode:New(data, it.pos.prev,
it.pos)
 89     it.pos.prev.next = node
 90     it.pos.prev
= node
 91     return CListIterator:New(node)
 92 end
 93
 94 function CList:Begin()
 95     return self:CreateIterator()
 96 end
 97
 98 function CList:End()
 99     return CListIterator:New(self.head)
100 end
101
102
103 function CList:PushFront(data)
104     self:Insert(self:Begin(),
data)
105 end
106
107 function CList:PushBack(data)
108     self:Insert(self:End(),
data)
109 end
110
111 function CList:IsEmpty()
112     return self:Begin().pos == self:End().pos
113 end
114
115 function CList:Erase(it)
116     assert(not it.data,
"you can't erase the head")
117     it.pos.prev.next = it.pos.next
118     it.pos.next.prev = it.pos.prev
119     it = nil
120 end
121
122 function CList:PopFront()
123     assert(not self:IsEmpty(),
"Can't PopFront to a Empty list")
124     self:Erase(self:Begin())
125 end
126
127 function CList:PopBack()
128     assert(not self:IsEmpty(),
"Can't PopBack to a Empty list")
129     self:Erase(self:End():MovePrev())
130 end
131
132 function CList:Clear()
133     while not self:IsEmpty()
do
134         self:Erase(self:Begin())
135     end
136 end
137
138 -- redefine
global print to support the CList

139 p = _G.print
140 function print(o)
141     if o ~= nil and type(o)
== "table" and 
142         o.type ~= nil and o.type ==
"CList" then
143         -- iterate like in C++ using CList and CListIterator feature
144         local it = o:CreateIterator()
145         while not it:IsEnd()
do
146             io.write(it:Cur().data)
147             io.write(" ")
148             it:MoveNext()
149         end
150         io.write("/n")
151     else
152         p(o)
153     end
154 end
155
156 -- test
PushFront

157 print("/ntest: test PushFront and PopFront")
158 newlist = CList:New()
159 newlist:PushFront(10)
160 print(newlist)
161 newlist:PushFront(20)
162 print(newlist)
163 newlist:PushFront(30)
164 print(newlist)
165 newlist:PopFront()
166 print(newlist)
167 it = newlist:CreateIterator()
168 newlist:Erase(it)
169 print(newlist)
170 newlist:Clear()
171 print(newlist)
172
173
174 -- test
PushBack

175 print("/ntest: test PushBack and popBack")
176 newlist = CList:New()
177 newlist:PushBack(10)
178 print(newlist)
179 newlist:PushBack(20)
180 print(newlist)
181 newlist:PushBack(30)
182 print(newlist)
183 newlist:PopBack()
184 print(newlist)
185 newlist:PopFront()
186 print(newlist)
187
188
189 -- test: insert
at begin

190 print("/ntest: insert at begin ")
191 newlist = CList:New()
192 it = newlist:CreateIterator()
193 iter = newlist:Insert(it, 10);
194 io.write("cur iterator:" ..  tostring(it.pos.data) .. "
return iterator:"
 .. tostring(iter.pos.data)
.. "/n")
195 print(newlist)
196 iter = newlist:Insert(it, 20);
197 io.write("cur iterator:" ..  tostring(it.pos.data) .. "
return iterator:"
 .. tostring(iter.pos.data)
.. "/n")
198 print(newlist)
199 iter = newlist:Insert(it, 30);
200 io.write("cur iterator:" ..  tostring(it.pos.data) .. "
return iterator:"
 .. tostring(iter.pos.data)
.. "/n")
201 print(newlist)
202
203 -- test: insert
at back

204 print("/ntest: insert at back")
205 newlist = CList:New()
206 it = newlist:CreateIterator()
207 it = newlist:Insert(it, 10);
208 io.write("cur iterator:" ..  tostring(it.pos.data).."/n")
209 it = newlist:Insert(it, 20);
210 io.write("cur iterator:" ..  tostring(it.pos.data).."/n")
211 it = newlist:Insert(it, 30);
212 io.write("cur iterator:" ..  tostring(it.pos.data).."/n")
213 print(newlist)
214
215 -- iterate like
in C++

216 print("/niterate like in C++")
217 it = newlist:CreateIterator()
218 while not it:IsEnd() do
219     io.write(it:Cur().data .. "
"
)
220     it:MoveNext()
221 end
222 print("/n")
223
224 -- closure list
iterator to iterate

225 print("/nclosure list iterator to iterate")
226 function list_iter(list)
227     local cur = list.head
228     return function()
229         if cur.next.data
~= nil then 
230             cur
= cur.next
231             return cur.data
232             end
233         end
234 end
235
236 for v in list_iter(newlist) do 
237     io.write(v .. "
"
)
238 end
239
240

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

阅读全文....

队列(queue)的链表(list)实现及循环数组(circular array)实现 C++实现


队列(queue)的链表(list)实现及循环数组(circular array)实现  C++实现

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构b与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第78-81面,堆栈的应用(1) 队列(queue)的链表(list)实现及循环数组(circular array) C++实现,需要注意的是,仅仅为了说明问题,没有详细探究代码的健壮,比如,我没有加入错误检测,这点在循环数组的实现是非常容易出现的。并且为了说明问题,我用了一个很小的数组来实现,以完成真正的从尾部到头部的跳转。

另外说明的是,书中队列应用一节我实在想不到有什么可以用代码简单实现的,所以都不写了。

详细情况见代码:

queue.h

  1 #ifndef __QUEUE_H__
  2 #define
__QUEUE_H__

  3 #include
<list>
  4 #include
<vector>
  5 using namespace std;
  6
  7 template<typename T>
  8 class CQueueSimple
  9 {
 10 public:
 11     bool empty() const
 12     {
 13         return moList.empty();
 14     }
 15     
 16     size_t size() const
 17     {
 18         return moList.size();
 19     }
 20
 21     void pop()
 22     {
 23         if(moList.empty())
 24         {
 25             throw -1;
 26         }
 27
 28         moList.pop_front();
 29     }
 30
 31     T&
front()
 32     {
 33         return moList.front();
 34     }
 35
 36     const T& front() const
 37     {
 38         return moList.front();
 39     }
 40
 41
 42     T&
back()
 43     {
 44         return moList.back();
 45     }
 46
 47     const T& back() const
 48     {
 49         return moList.back();
 50     }
 51
 52     void push(const T&
aItem)
 53     {
 54         moList.push_back(aItem);
 55     }
 56
 57 private:
 58     list<T>
moList;
 59 };
 60
 61 //
implement a queue with circular array

 62 // there
is no error check.

 63 template<typename T, size_t ArraySize>
 64 class CQueueCir
 65 {
 66 public:
 67     CQueueCir()
 68     {
 69         // init to zero
 70         memset(maData,
0, ArraySize * sizeof(T)
);
 71         mpFront
= mpBack = maData + ArraySize/2;
 72     }
 73
 74
 75     bool empty() const
 76     {
 77         return !(mpBack - mpFront);
 78     }
 79     
 80     size_t size() const
 81     {
 82         return (mpBack - mpFront);
 83     }
 84
 85     void pop()
 86     {
 87         if(empty())
 88         {
 89             throw -1;
 90         }
 91
 92         ++mpFront;
 93         RollToHead(&mpFront);
 94     }
 95
 96     T& front()
 97     {
 98         return *mpFront;
 99     }
100
101     const T& front() const
102     {
103         return *mpFront;
104     }
105
106
107     T& back()
108     {
109         return *(mpBack-1);
110     }
111
112     const T& back() const
113     {
114         return *(mpBack-1);
115     }
116
117     void push(const T&
aItem)
118     {
119         *mpBack++
= aItem;
120         RollToHead(&mpBack);
121     }
122
123
124 private:
125     void RollToHead(T** ap)
126     {
127         if(size_t(*ap
- maData) >= ArraySize)
128         {
129             *ap
= maData;
130         }
131     }
132
133     T
maData[ArraySize];
134     
135     // Hold the important position
136     T* mpFront;
137     T* mpBack;
138 };
139
140 #endif

 

 

测试代码:

 1 #include <stdio.h>
 2 #include
<stdlib.h>
 3 #include
<iostream> 
 4 #include
"Queue.h"
 5
 6 #define
OUT(queue) /

 7     cout
<<
"front: " <<queue.front() <<",back: " <<queue.back()
<<
",size: " <<queue.size() <<endl
 8
 9 template<typename Queue>
10 void test(Queue&
aoQueue)
11 {
12     aoQueue.push(1);
13     OUT(aoQueue);
14
15     aoQueue.push(2);
16     OUT(aoQueue);
17
18     aoQueue.push(3);
19     OUT(aoQueue);
20
21     aoQueue.pop();
22     OUT(aoQueue);
23
24     aoQueue.pop();
25     OUT(aoQueue);
26
27     aoQueue.push(4);
28     OUT(aoQueue);
29 }
30
31 int main(int argc, char*
argv[])
32 {
33     CQueueSimple<int> liQ;
34     test(liQ);
35     cout
<<endl;
36
37     CQueueCir<int, 3>
liQCir;
38     test(liQCir);
39
40     exit(0);
41 }
42

 

 

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

阅读全文....

堆栈的应用(2) 中缀算术表达式到后缀(逆波兰记法reverse polish notation)的转换及其计算 C++实现


 堆栈的应用(2
中缀算术表达式到后缀(逆波兰记法reverse polish notation)的转换及其计算 C++实现

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第73-77面,中缀算术表达式到后缀(逆波兰记法reverse polish notation)的转换及其计算

       目前仅仅实现文中说明的功能,目标并不是一个完整的四则运算程序,所以只支持加法,乘法和()。另外,因为对于C++流的控制能力比较弱(我下一步就决定好好研究研究),所以对输入的格式要求非常严格。

必须是1 + 2 * 3 =

的格式,每个数字和符号之间都需要空格,一个比较复杂的例子是:

1 + 2 *
3 + ( 1 + 2 * 3 ) =

转换后:

1 2 3 *
+ 1 2 3 * + + =

先看测试程序,就应该能知道,大概实现了什么效果了,这里唯一的便利在于,用了C++的输入输出流后,对于iostream,stringstream都比较一致了,但是还是感觉自己对流的控制能力太弱了。

test.cpp:

 1 #include <stdio.h>
 2 #include
<stdlib.h>
 3 #include
<stack>
 4 #include
<string> 
 5 #include
<iostream> 
 6 #include
<sstream>
 7 #include
"ExprComputer.h"
 8 using namespace std;
 9
10 int main(int argc, char*
argv[])
11 {
12     CExprComputer
loExprComputer;
13     // all these below can work right,comment is same as the
content 'couted'.

14     stringstream lss;
15     lss << "1 + 2 * 3 =";
16
17     cout <<"test trans stringstream in and cout." <<endl;
18     loExprComputer.TransInfix2Postfix(lss,
cout);
19
20     cout <<"test trans cin and cout." <<endl;
21     loExprComputer.TransInfix2Postfix(cin,
cout);
22
23     stringstream
lss2;
24     cout <<"test trans cin and stringstream out." <<endl;
25     loExprComputer.TransInfix2Postfix(cin,
lss2);
26     cout
<<lss2.str() <<endl;
27
28     lss.seekg(0);
29     cout <<"test stringstream in computeInfix." <<endl;
30     cout
<<lss.str();
31     cout
<<loExprComputer.ComputeInfix(lss) <<endl;
32
33     cout <<"test cin in computeInfix." <<endl;
34     cout
<<loExprComputer.ComputeInfix(cin) <<endl;
35
36     stringstream
lssPostfix;
37     lssPostfix
<< "1 2 3 * + =";
38     cout <<"test stringstream in ComputePostfix." <<endl;
39     cout
<<lssPostfix.str();
40     cout
<<loExprComputer.ComputePostfix(lssPostfix) <<endl;
41
42     cout <<"test cin in ComputePostfix." <<endl;
43     cout
<<loExprComputer.ComputePostfix(cin) <<endl;
44  
45     cout <<"Test completed." <<endl;
46     exit(0);
47 }
48

 

 

ExprComputer头文件:

1 #ifndef __EXPR_COMPUTE_H__
 2 #define
__EXPR_COMPUTE_H__

 3 #include
<iostream> 
 4 #include
<sstream>
 5 #include
<stack> 
 6 using namespace std;
 7
 8 // argument
to input

 9 #define
_IN_

10
11 // argument to
output

12 #define _OUT_
13
14 class CExprComputer
15 {
16 public:
17     int ComputeInfix(_IN_ istream&
aisExpr);
18     int ComputePostfix(_IN_ istream&
aisExpr);
19
20     // Transform a infix expression to Postfix expression
21     int TransInfix2Postfix(_IN_ istream&
aisInfix,
22             _OUT_
ostream& aosPostfix);
23
24 private:
25     // Stack should be empty,Dump the information still in Stack
and exit

26     void DumpStack();
27
28     // Output all information still in Stack
29     void OutputStack();
30
31     // Make sure Stack is not empty when it should not.
32     void CheckStack();
33
34     // I don't know why Stack operator is so few.And why I need
to

35     // clear the Stack in this example? GOD knows.
36     void ClearStack();
37
38     // Read a int or a operator from a stream
39     bool ReadStream(_IN_ istream&
aisExpr, _OUT_ int&
aiReaded,  _OUT_ bool&
abIsChar);
40
41     // Process a Operator
42     void ProcessOperator(char ac, _OUT_ ostream& aosPostfix);
43
44     void ComputeOperator(char ac);
45
46     stack<int> miSta;
47 };
48
49
50
51
52
53 #endif
54

 

cpp 文件:

  1 #include "ExprComputer.h"
  2
  3 void CExprComputer::DumpStack()
  4 {
  5     if(!miSta.empty())
  6     {
  7         cout
<<"stack: ";
  8         OutputStack();
  9         cout
<<endl;
 10         exit(1);
 11     }
 12
 13 }
 14
 15 void CExprComputer::OutputStack()
 16 {
 17     while(!miSta.empty())
 18     {
 19         cout
<<miSta.top() <<" ";
 20         miSta.pop();
 21     }
 22 }
 23
 24 void CExprComputer::ClearStack()
 25 {
 26     while(!miSta.empty())
 27     {
 28         miSta.pop();
 29     }
 30 }
 31
 32 void CExprComputer::CheckStack()
 33 {
 34     if(    miSta.empty() )
 35     {
 36         cout
<<"Invalid expression input." <<endl;
 37         exit(1);
 38     }
 39 }
 40
 41 bool CExprComputer::ReadStream(_IN_
istream& aisExpr, _OUT_ int&
aiReaded,  _OUT_ bool&
abIsChar)
 42 {
 43     if(aisExpr.eof())
 44     {
 45         return false;
 46     }
 47
 48     // try to read stream as a int
 49     abIsChar = false;
 50     int li;
 51     aisExpr
>> li;
 52
 53     // if next thing in stream is not a int, back a char and
read it

 54     if(aisExpr.fail())
 55     {
 56         aisExpr.clear();
 57         aisExpr.unget();
 58         char c;
 59         aisExpr
>> c;
 60         if(c != '=')
 61         {
 62             aiReaded
= c;
 63             abIsChar
= true;
 64             return true;
 65         }
 66         else
 67         {
 68             return false;
 69         }
 70     }
 71
 72     aiReaded =
li;
 73     return true;
 74 }
 75
 76
 77 void CExprComputer::ProcessOperator(char ac, _OUT_ ostream& aosPostfix)
 78 {
 79     switch(ac)
 80     {
 81         case '(':
 82         {
 83             // save the '('
 84             miSta.push(ac);
 85             break;
 86         }
 87         case ')':
 88         {
 89             char lc;
 90             CheckStack();
 91
 92             // output all operator until find a '('
 93             while( (lc = miSta.top()) != '(' )
 94             {
 95                 aosPostfix
<< lc <<" ";
 96                 miSta.pop();
 97                 CheckStack();
 98             }
 99
100             // the first '(' in stack,We just need pop it
101             miSta.pop();
102             break;
103         }
104         case '*':
105         {
106             char lc;
107
108             // output all operator until find a lower level operator
109             while( !miSta.empty() &&
110                     ((lc
= miSta.top()) != '(') &&
111                     (
lc != '+') )
112             {
113                 aosPostfix
<<lc <<" ";
114                 miSta.pop();
115             }
116
117             miSta.push(ac);
118             break;
119         }
120         case '+':
121         {
122
123             char lc;
124
125             // output all operator until find a lower level operator
126             while( !miSta.empty() &&
127                     ((lc
= miSta.top()) != '(') )
128             {
129                 aosPostfix
<<lc <<" ";
130                 miSta.pop();
131             }
132
133             miSta.push(ac);
134             break;
135         }
136         default:
137         {
138             cout
<<"Don't support this operator." <<endl;
139             exit(1);
140         }
141     }
142
143 }
144
145 int CExprComputer::TransInfix2Postfix(_IN_
istream& aisInfix,
146         _OUT_
ostream& aosPostfix)
147 {
148     int li = 0;
149     bool lbIsChar = false;
150     while( ReadStream(aisInfix, li, lbIsChar) )
151     {
152         // number need immediately output
153         if(!lbIsChar)
154         {
155             aosPostfix
<<li <<" ";
156         }
157         else
158         {
159             char lc = static_cast<char>(li);
160             ProcessOperator(lc,
aosPostfix);
161         }
162     }
163
164     while(!miSta.empty())
165     {
166         aosPostfix
<<(char)miSta.top() <<" ";
167         miSta.pop();
168     }
169     aosPostfix
<<'=' <<endl;
170
171     return 1;
172 }
173
174 int CExprComputer::ComputePostfix(_IN_
istream& aisExpr)
175 {
176     ClearStack();
177
178     int li = 0;
179     bool lbIsChar = false;
180     while( ReadStream(aisExpr, li, lbIsChar) )
181     {
182         // number need immediately output
183         if(!lbIsChar)
184         {
185             miSta.push(li);
186         }
187         else
188         {
189             char lc = static_cast<char>(li);
190             ComputeOperator(lc);
191         }
192     }
193
194     CheckStack();
195     int liResult = miSta.top();
196     miSta.pop();
197
198     DumpStack();
199
200     return liResult;
201 }
202
203 void CExprComputer::ComputeOperator(char ac)
204 {
205     // get lhs and rhs
206     CheckStack();
207     int lilhs = miSta.top();
208     miSta.pop();
209     CheckStack();
210     int lirhs = miSta.top();
211     miSta.pop();
212
213     switch(ac)
214     {
215         case '*':
216         {
217             int liResult = lilhs * lirhs;
218             miSta.push(liResult);
219             break;
220         }
221         case '+':
222         {
223             int liResult = lilhs + lirhs;
224             miSta.push(liResult);
225             break;
226         }
227         default:
228         {
229             cout
<<"Don't support this operator." <<endl;
230             exit(1);
231         }
232     }
233 }
234
235 int CExprComputer::ComputeInfix(_IN_
istream& aisExpr)
236 {
237     stringstream
lss;
238     TransInfix2Postfix(aisExpr,
lss);
239     return ComputePostfix(lss);
240 }

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

阅读全文....

堆栈的简单C++实现

 

堆栈的简单C++实现

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 头文件:

 1 #ifndef __STACK_H__
 2 #define
__STACK_H__

 3 #include
<iostream> 
 4 #include
<vector>
 5 using namespace std;
 6
 7 template<typename T>
 8 class CStack
 9 {
10 public:
11     CStack() { }
12     ~CStack() { }
13
14     size_t empty()
15     {
16         return miDataVec.empty();
17     }
18
19     size_t size()
20     {
21         return miDataVec.size();
22     }
23
24     void pop()
25     {
26         miDataVec.pop_back();
27     }
28
29     T& top()
30     {
31         return miDataVec.back();
32     }
33
34     const T& top() const
35     {
36         return miDataVec.back();
37     }
38
39     void push(const T&
aItem)
40     {
41         miDataVec.push_back(aItem);
42     }
43 private:
44     vector<T>
miDataVec;
45
46 };
47
48
49
50
51
52
53 #endif
54

 

测试程序:

 1 #include <stdio.h>
 2 #include
<stdlib.h>
 3 #include
<iostream> 
 4 #include
"stack.h"
 5 using namespace std;
 6
 7
 8 int main(int argc, char*
argv[])
 9 {
10     CStack<int> loStack;
11
12     loStack.push(1);
13     cout
<<loStack.top() <<" ";
14
15     loStack.push(2);
16     cout
<<loStack.top() <<" ";
17
18     loStack.push(1);
19     cout
<<loStack.top() <<" ";
20
21     loStack.push(2);
22     cout
<<loStack.top() <<" ";
23
24     loStack.push(3);
25     cout
<<loStack.top() <<" ";
26     
27     loStack.push(4);
28     cout
<<loStack.top() <<" ";
29
30     cout
<<endl;
31
32     while(loStack.size() != 0)
33     {
34         cout
<<loStack.top() <<" ";
35         loStack.pop();
36     }
37
38     cout
<<endl;
39
40     exit(0);
41 }
42

 

 

这里顺便说明一下,这个实现仅仅是为了说明问题。

C++中标准的stack实现是通过adaptor设计模式来实现的,并将用于实现的容器放入了模板的参数,以方便你用vectorlist,来替代默认的deque

 

 

 

 

 

 

 

 

 

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

阅读全文....

堆栈的应用(1) 平衡符号 C++实现

 

  堆栈的应用(1) 平衡符号 C++实现

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第72面,堆栈的应用(1) 平衡符号

 

 1 #include <stdio.h>
 2 #include
<stdlib.h>
 3 #include
<stack>
 4 #include
<string> 
 5 #include
<iostream> 
 6 using namespace std;
 7
 8 bool CheckStack(const char ac,
stack<char>& acSta)
 9 {
10     if(ac == '(' ||
ac == '[')
11     {
12         acSta.push(ac);
13     }
14     else if(ac
== ')')
15     {
16         if( acSta.empty() || acSta.top() != '(' )
17         {
18             return false;
19         }
20         acSta.pop();
21     }
22     else if(
ac == ']')
23     {
24         if(acSta.empty() || acSta.top() != '[' )
25         {
26             return false;
27         }
28         acSta.pop();
29     }
30
31     return true;
32 }
33
34 void DumpStack(stack<char>& acSta)
35 {
36     if(!acSta.empty())
37     {
38         cout
<<"stack: ";
39         while(!acSta.empty())
40         {
41             cout
<<acSta.top() <<" ";
42             acSta.pop();
43         }
44         cout
<<endl;
45     }
46 }
47
48 int main(int argc, char*
argv[])
49 {
50     char lc;
51     stack<char> lcSta;
52     while(cin >> lc)
53     {
54         if(!CheckStack(lc, lcSta))
55         {
56             cout
<<"Error happen: " <<lc
<<endl;
57             DumpStack(lcSta);
58             exit(1);
59         }
60     }
61
62     DumpStack(lcSta);
63
64     exit(0);
65 }
66

 

 

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

阅读全文....