你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

第1关:栈的应用 - 计算中缀表达式

2021-11-13 16:36:44

样例输入: (1+2)*(9-6) 样例输出: result = 9.000000

基本思路:

1、遇到数字进栈;

2、遇到( 进栈;

3、遇到+或-,判断栈顶元素是不是(,是就进栈,不是就计算,确保在+-入栈前,前面的运算都已完成;

4、遇到*或/,如果栈顶元素是*或/就计算,否则进栈

5、遇到),如果栈顶元素不是(,就进行计算,直到遇到(为止。

6、最后将剩余的运算符进行计算

double ComputeInfix(char* s)
//计算中缀表达式
{
    // 请在此添加代码,补全函数ComputeInfix,计算中缀表达式
    /********** Begin *********/
	int i=0;
	LinkStack* so= LS_Create();
	LinkStack* sd= LS_Create();
	double res;
	while(s[i])
	{
		T top;
		if(s[i]>='0'&&s[i]<='9')
		{
			LS_Push(sd,s[i++]-48);
			continue;
		} 
		if(s[i]=='(')
		{
			LS_Push(so,s[i++]); 
			continue;
		} 
		if(s[i]==')')
		{
			while(LS_Top(so,top)&&top!='(')	//确保()中的计算式计算完全
			{
				compute(so,sd);
			}
			LS_Pop(so,top); 	//将'('出栈
			i++;
			continue;
		}
		if(s[i]=='*'||s[i]=='/')
			{
				T top;
				LS_Top(so,top);
				if(top=='*'||top=='/') compute(so,sd);
				LS_Push(so,s[i++]);
				continue;
			}
		if(s[i]=='+'||s[i]=='-')
			{
				T top;
				while(LS_Top(so,top)&&top!='(') 
				{
					compute(so,sd);//确保+或-在入栈前,*/先进行了运算
				}	
				LS_Push(so,s[i++]);
				continue;
			}
	}
	while(!LS_IsEmpty(so))	compute(so,sd);	//将剩余的运算符进行运算	
	LS_Top(sd,res);
	return res;
    /********** End **********/
}