MFC项目一：基于逆波兰表达式的计算器

知识基础：

我们平时所见到的，类似于（2+9）*6的计算式，都可称之为中缀表达式，其双目运算符位于两个操作数之间；而逆波兰表达式又可称为后缀表达式，其操作符位于两个操作数之后，例如 1+1 -> 11+，（2+9）*6 -> 29+6*。在进行计算时，从左到右遍历算式遇到操作数即压入数栈，遇到操作符即从数栈中弹出两个数字进行计算，再将结果压入栈中，由于其可通过有序遍历得到结果这一特征，故算式计算中，一般需将中缀表达式转为后缀表达式，再按相应规则计算出结果。

至于转化方法，首先明确的是，由于计算时从左到右遍历，故优先级高的运算符位置要靠前，前面两个数字（包括之前运算符生效时产生的结果）是它的操作对象。为了达到这个目标，我们还需准备一个符号的暂存栈，之后从左至右遍历中缀表达式，遇到数字放入中缀表达式post，遇到符号时，优先于栈顶元素则压入符号栈；反之则不断将栈顶元素放入post，直到满足优先度或栈空（由于同级运算符的左结合性，必须优先而非大于等于），遍历完成后，如果栈中有剩余则依次弹出放入post（这种顺序保证，优先级较高符号再前）；如果存在括号时，则需将括号中的部分视作一个独立的算式，即遇到右括号时，要依次清空符号栈（等价于左括号优先级最大，右括号优先级最小）。

实际项目编写中，我们令一个输入编辑框添加CString 变量储存中缀表达式，表达式转化和计算均写入等号按钮的按动函数中。

核心代码：

void CcaculatorDlg::OnBnClickedButton16()
{

	// TODO: 在此添加控件通知处理程序代码
	int p1=0,p2=0,p=0;	//p2数字栈的下标,p1符号栈下标
	char sym[100];
	double num[100];
	std::vector<std::string>post;
	int len=str.GetLength();

	
	//中缀表达式转后缀表达式，存入vector<string>post
	//如果首位为负数，则理解为前面补零
	if(str[0]=='-'){
		str='0'+str;
	}
	while(p<len){
		if(str[p]<='9'&&str[p]>='0'){
			std::string num;
			while((str[p]<='9'&&str[p]>='0')||str[p]=='.')
				num+=str[p++];
			post.push_back(num);
			p--;
		}else if(str[p]=='('){
			sym[p1++]='(';
		}else if(str[p]==')'){
			char tmp[2]={0};	
			tmp[0]=sym[p1-1];
			while(tmp[0]!='('){
				std::string strtmp(tmp);
				post.push_back(strtmp);
				tmp[0]=sym[--p1-1];
			}
			p1--;
		}else if(str[p]=='+'||str[p]=='-'){
			char tmp[2]={0};
			while(p1>0){
				tmp[0]=sym[p1-1];
				if(tmp[0]=='(')
					break;
				p1--;
				post.push_back(std::string(tmp));
			}
			sym[p1++]=str[p];
		}else if(str[p]=='*'||str[p]=='/'){
			char tmp[2]={0};
			while(p1>0){
				tmp[0]=sym[p1-1];
				if(tmp[0]=='('||tmp[0]=='+'||tmp[0]=='-')
					break;
				p1--;
				post.push_back(std::string(tmp));
			}
			sym[p1++]=str[p];
		}
		p++;
	}
	while(p1>0){
		char tmp[2]={0};
		tmp[0]=sym[--p1];
		post.push_back(std::string(tmp));
	}

	//计算
	double num1,num2;
	std::vector<std::string>::iterator it;
	std::string strtmp;
	for(it=post.begin();it!=post.end();it++){
		strtmp=(*it);
		if(strtmp=="+"||strtmp=="-"||strtmp=="*"||strtmp=="/")
			num1=num[--p2],num2=num[--p2];
		if(strtmp=="+")
			num[p2++]=num2+num1;
		else if(strtmp=="-")
			num[p2++]=num2-num1;
		else if(strtmp=="*")
			num[p2++]=num2*num1;
		else if(strtmp=="/")
			num[p2++]=num2/num1;
		else
			num[p2++]=atof((*it).c_str());
	}
	if(str=="")
		ans=0;
	else
		ans=num[0];
	
	UpdateData(FALSE);
}