中缀表达式

不含括号的中缀表达式

代码实现

//直接计算中缀表达式
//不含括号
#include<iostream>
#include<stack>
#include<string>

using namespace std;

//运算符号优先级比较
//加减为低级运算，乘除是高级运算；先算乘除
//return 1 means can calculate, else can not.
int getPriority( stack<char> operators )
{
	if( !operators.empty()  && ( operators.top() == '*' || operators.top() == '/') ){
		return 1;
	}

	return 0;
}


//输入操作符栈 和 操作数栈 进行计算
void calculate(stack<double> &operands, stack<char> &operators)
{
	double op1, op2, res;
	char operation;

	op2 = operands.top();
	operands.pop();
	op1 = operands.top();
	operands.pop();

	operation = operators.top();
	operators.pop();

	switch( operation ){
		case '+':
			res = op1 + op2;
			break;
		case '-':
			res = op1 - op2;	//对顺序有要求
			break;
		case '*':
			res = op1 * op2;
			break;
		case '/':
			res = op1 / op2;	//这个顺序不能反
			break;
	
	}

	//cout << op1 << operation << op2 << "=" << res << endl;	//test
	operands.push(res);

}


int main()
{
	stack<double> operands;	//除法运算可能会出现小数
	stack<char> operators;

	string formula;
	string number;

	const string numbers = "0123456789";
	const string operation = "+-*/";

	cin >> formula;
	for( string::iterator c = formula.begin();  c != formula.end();  c++ ){

		//处理数字
		if( numbers.find(*c) != string::npos ){
			while( numbers.find(*c) != string::npos ){
				number += *c;
				c++;
			} 
			operands.push( stod(number) );
			number.clear();

		       //读完最后一个数字
			if ( c == formula.end() ){
				if( getPriority(operators) == 1 ){	//最后一个操作符可能是乘除
					calculate(operands, operators);
				}
				break;	
			}
		}

		//calculate, 先算乘除
		if( operation.find(*c) != string::npos ){
			if ( getPriority(operators)  ==  1 ){
				calculate( operands, operators );
			}
			operators.push((*c));
		}
	}


	//处理剩余的加减
	while( !operators.empty() ){
		char operation = operators.top();

		//减法有顺序要求;1-2+3,先执行1-2=-1，再执行-1+3
		if( operation == '+' ){
			operators.pop();
			if( !operators.empty()  &&  operators.top() == '-' ){
				double tmp = operands.top();
				operands.pop();

				calculate( operands, operators );

				operators.push(operation);
				operands.push(tmp);
			}	
			else{
				operators.push(operation);
				calculate( operands, operators );
			}

		}
		else{
			calculate( operands, operators );
		}

	}
	
	cout << formula << " = " << operands.top() << endl;
	return 0;
}

---

含括号的中缀表达式代码实现

//直接计算中缀表达式
//含括号
#include<iostream>
#include<deque>
#include<string>

using namespace std;


//运算符号优先级比较
//return 1 means can calculator, else can not.
int getPriority( deque<char> operators )
{
	if( !operators.empty()  && ( operators.back() == '*' || operators.back() == '/') ){
		return 1;
	}

	return 0;
}


double calculate( double op1, double op2, char operation )
{
	double res;

	switch( operation ){
		case '+':
			res = op1 + op2;
			break;
		case '-':
			res = op1 - op2;	//对顺序有要求
			break;
		case '*':
			res = op1 * op2;
			break;
		case '/':
			res = op1 / op2;	//这个顺序不能反
			break;
	}

	//cout << op1 << operation << op2 << "=" << res << endl;	//test

	return res;
}

void calculator(deque<double> &operands, deque<char> &operators)
{
	double op1, op2, res;
	char operation;

	operation = operators.back();
	operators.pop_back();

	//这个糟糕的顺序
	if( operation == '-' ){
		op1 = operands.back();
		operands.pop_back();
		op2 = operands.back();
		operands.pop_back();
	}else{
		op2 = operands.back();
		operands.pop_back();
		op1 = operands.back();
		operands.pop_back();
	}


	res = calculate( op1, op2, operation );

	operands.push_back(res);
}




int main()
{
	deque<double> operands;	//除法运算可能会出现小数; 使用deque，比栈更灵活
	deque<char> operators;

	string formula;
	string number;

	const string numbers = "0123456789";
	const string Operation = "+-*/";

	cin >> formula;
	for( string::iterator c = formula.begin();  c != formula.end();  c++ ){

		//处理数字
		if( numbers.find(*c) != string::npos ){
			while( numbers.find(*c) != string::npos ){
				number += *c;
				c++;
			} 
			operands.push_back( stod(number) );
			number.clear();

		       //读完最后一个数字
			if ( c == formula.end() ){
				if( getPriority(operators) == 1 ){	//最后一个可能是乘除
					calculator(operands, operators);
				}
				break;	
			}
		}

		//处理 + - * /
		if( Operation.find(*c) != string::npos ){
			//calculator, 先算乘除
			if ( getPriority(operators)  ==  1 ){
				calculator( operands, operators );
			}
			operators.push_back((*c));
		}
		//处理括号
		else{
			if( *c == '(' ){
				operators.push_back((*c));
			}
			//遇到)”时,算出()内算式的值
			else{	
				//)前面可能是乘除
				if(  getPriority(operators) == 1 ){
					calculator(operands, operators);
				}

				//此时括号内已经没有乘除
				deque<double> tmp_oprands;
				deque<char> tmp_operators;
				//把()内的算式pop到新的栈
				while( operators.back() != '(' ){
					tmp_oprands.push_back(operands.back());
					operands.pop_back();
					
					tmp_operators.push_back(operators.back());
					operators.pop_back();
				}
				tmp_oprands.push_back(operands.back());
				operands.pop_back();
				operators.pop_back();	//弹出“(”
				
				while(!tmp_operators.empty()){	//计算括号内的算式
					calculator( tmp_oprands, tmp_operators );
				}

				operands.push_back( tmp_oprands.back() );	//push结果
				tmp_oprands.pop_back();

			}
		
		}
	}


	//处理剩余的加减
	double op1, op2, res;
	char operation;
	while( !operators.empty() ){

		//因为前面使用的是deque结构而不是stack，所以这里可以从栈底开始读取
		//(考虑到减法运算过程中的y顺序要求)
		op1 = operands.front();
		operands.pop_front();
		op2 = operands.front();
		operands.pop_front();

		operation = operators.front();
		operators.pop_front();

		res = calculate( op1, op2, operation);

		operands.push_front(res);
	}
	
	cout << formula << " = " << operands.back() << endl;
	return 0;
}

改进

前面的算法将加减与乘除分开处理，导致后面运算加减的时候还要考虑减法的运算顺序问题，变得麻烦了。
下面是改进后的代码

#include<iostream>
#include<string>
#include<stack>

using namespace std;


//return the answer of op1 operation op2
double calculate( double op1, double op2, char operation )
{
	double res;

	switch(operation){
		case '-':
			res = op1 - op2;
			break;
		case '+':
			res = op1 + op2;
			break;
		case '*':
			res = op1 * op2;
			break;
		case '/':
			res = op1 / op2;
			break;
	}
	
	cout << op1 << operation << op2 << " = " << res << endl;	//test
	return res;
}


int getPriority( char operation )
{
	//这个优先级很微妙
	if ( operation == '(' )
		return 1;
	else if( operation == '+' ||  operation == '-' )
		return 2;
	else if( operation == '*' ||  operation == '/' )
		return 3;
}

void calculator( stack<double> &operands,  stack<char> &operators )
{
	double op1, op2, ans;
	char operation;

	op2 = operands.top();
	operands.pop();
	op1 = operands.top();
	operands.pop();

	operation = operators.top();
	operators.pop();

	ans = calculate( op1, op2, operation );

	operands.push(ans);
}


//(1+2)*33-8/2-9

int main()
{
	const string Numbers = "0123456789";
	const string Operators = "+-*/";

	stack<double> operands;
	stack<char> operators;

	string formula;

	cin >> formula;

	for( string::iterator c = formula.begin(); c != formula.end();  c++ ){
	

		//字符转数字
		if( Numbers.find(*c) != string::npos ){
			string num;
			while( c != formula.end()  &&   Numbers.find(*c) != string::npos ){
				num += *c;
				c++;
			}
			c--;	//退一步
			operands.push( stod(num) );
			//cout << operands.top() << endl;	//test
		}
		//运算
		else if( Operators.find(*c) != string::npos ){
			if( operators.empty() )	
				operators.push(*c);
			else{
				//这里while很关键
				while( !operators.empty()  &&  getPriority(operators.top()) >= getPriority(*c) ){
					calculator( operands, operators);
				}
				operators.push(*c);
			}
		}
		//括号处理
		else{
			if( *c == '(' )
				operators.push(*c);
			else{
				while( operators.top() != '(' ){
					calculator( operands, operators);
				}
				operators.pop();
			}
		}
	}


	while( !operators.empty() ){
		calculator( operands, operators );
	}

	cout << formula << " = " << operands.top() << endl;
	return 0;
}