C++表达式求值（利用数据结构栈）

唉，刚刚用C++又重新写了一个较完善的表达式求值程序，最后精简后程序还不到100行，这不经让我

想到了大一上学期刚学c语言时自己费了好大的劲，写了几百行而且功能还不是很齐全(当时还不能计算有括号的表

达式)的简单计算器程序。刚把两个程序对比了一下，感触还是挺深的，同时也再一次体现了数据结构在程序设计

中的重要性。

以前的那个程序有漏洞而且逻辑复杂，所以就不提了，只说说现在改进后的程序，其思想主要是用到了

栈先进后出的数据结构。在该程序中建有两个栈：一个用于存储运算符，另一个用于存储操作数或运算结果。基本

过程是：

（1）：首先设置操作数栈为空栈，设置运算符栈以‘#’为栈底元素（其优先级最低）。

（2）：通过为栈内栈外运算符设置值而比较其优先级

（3）：依次去找到表达式中的所有运算符和操作数，对于操作数直接入栈，运算符则和运算符栈的

栈顶运算进行比较优先级，若栈内优先级大，则进行相应操作并操作数和栈内运算符都出栈，若优先级相等只需

栈内运算符出栈继续查找下一个运算符即可，若栈内优先级低则栈外运算符入栈。依次循环知道分析完表达式中

的所有运算符和操作数即可。

（4）：最后在操作数栈中将只会剩下唯一的一个元素，而该元素也将就会是所求表达式的值。

#include
  
   
#include
   
     #include
    
      using namespace std; /*判断符号间的优先关系函数 *1表示>,0表示=,-1表示< *c1栈内的算符，c2栈外的算符 */ int Judge(char c1,char c2) { int a1,a2; if('+'==c1||'-'==c1) a1 = 3; if('*'==c1||'/'==c1)a1 = 5; if('('==c1) a1 = 1; if(')'==c1) a1 = 7; if('#'==c1) a1 = 0; if('+'==c2||'-'==c2)a2 = 2; if('*'==c2||'/'==c2)a2 = 4; if('('==c2) a2 = 6; if(')'==c2) a2 = 1; if('#'==c2) a2 = 0; if(a1>a2) return 1; if(a1==a2) return 0; if(a1
     
      >str; //给表达式字符串str添加'#'结束标识符 str.append(1,'#'); stack
      
        OPTR;//运算符栈 stack
       
         OPND;//操作数栈 int a = -1; //先将#符号入栈 OPTR.push('#'); while(true) { int b = a+1; a = str.find_first_of(op,a+1); if(a==string::npos) break; if(a!=b) { string ss(str,b,a-b); double d=atof(ss.c_str()); //数据先入栈 OPND.push(d); } //运算符优先级比较 int ju = Judge(OPTR.top(),str[a]); if(-1==ju)//栈外优先级大直接入栈 { OPTR.push(str[a]); } if(0==ju)//栈内外优先级相等则出栈 { OPTR.pop(); } if(1==ju)//栈内优先级大,出栈进行运算 { double d1 = OPND.top(); OPND.pop(); double d2 = OPND.top(); OPND.pop(); d1 = run(OPTR.top(),d2,d1); //运算结果入栈 OPND.push(d1); OPTR.pop(); a--; } } //删除表达式最后的'#'结束标识符 str.erase(str.length()-1,1); cout<