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

怼烎@ 2022-03-30 12:20 206阅读 0赞

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

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

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

中的重要性。

曾经的那个程序有漏洞并且逻辑复杂，所以就不提了，仅仅说说如今改进后的程序，其思想主要是用到了

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

过程是：

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

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

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

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

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

的全部运算符和操作数就可以。

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

#include<iostream>
    #include<stack>
    #include<string>
    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<a2) return -1;
    }
    //符号运算函数
    double run(char c ,double d1,double d2)
    {
    	switch (c)
    	{
    	case '+':
    		return d1+d2;
    		break;
    	case '-':
    		return d1-d2;
    		break;
    	case'*' :
    		return d1*d2;
    		break;
    	case '/':
    		return d1/d2;
    		break;
    	default:
    		return 0.0;
    		break;
    	}
    }
    int main()
    {
    	char * op = "+-*/()#";
    	string str ;
    	cin>>str;
    	//给表达式字符串str加入'#'结束标识符
    	str.append(1,'#');
    	stack<char> OPTR;//运算符栈
    	stack<double> 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<<str<<" = "<<OPND.top()<<endl;
    }

![SouthEast][]

[SouthEast]: /images/20220330/7beb07edcf6c4bd894c1c1d72db17bd8.png