用顺序栈计算只含加减乘除和括号的表达式代码,C代码库,德仔网

代码语言
代码分类
【C】用顺序栈计算只含加减乘除和括号的表达式
作者:Chenyz / 发布于2011/9/18/ 693
用C++语言实现，希望大家给出优化意见
<div>
<pre>
//use seqStack to solve Expression Resolve

#include<stack>
#include<vector>
#include<iostream>
#include<string>
using namespace std;

const string supportedOperator = "+-*/()";

// '+' '-' '*' '/' '(' ')' 
const int precede[6][6] = {
	{1,1,-1,-1,-1,1},
	{1,1,-1,-1,-1,1},
	{1,1,1,1,-1,1},
	{1,1,1,1,-1,1},
	{-1,-1,-1,-1,-1,0},
	{1,1,1,1,2,1}
};
	
//push input into the inorder vector
void input(vector<char>&);

//change inorder expression to postorder expression
void convert(const vector<char>&, vector<char>&);

//calculate return the expression's value
int calc(const vector<char>&);

//return ture when '(', ')', '+', '-', '*', '/'
bool isOperator(const char);

//return operator's index in supportedOperator
int getIndex(const char);

//return int value from postorder vector
int calcOperand(const vector<char>&, vector<char>::const_iterator&);

int main(){
	vector<char> inorder, postorder;
	string prompt="Input a express and end with ctrl+Z:\n";

	cout<<prompt;
	input(inorder);
	convert(inorder, postorder);
	cout<<calc(postorder)<<endl;

	return 0;
}

void input(vector<char>& inorder){
	char temp;
	while(cin>>temp){
		inorder.push_back(temp);
	}
}

void convert(const vector<char>& inorder, vector<char>& postorder){
	stack<char> _operator;
	vector<char>::const_iterator i;
	for(i=inorder.begin(); i!=inorder.end(); ++i){
		if( isdigit(*i) ){
			postorder.push_back(*i);
		}
		if( isOperator(*i) ){
			if(!postorder.empty() && postorder.back()!=' '){
				postorder.push_back(' ');
			}
			if(*i == '('){
				_operator.push(*i);
			}
			else if(*i == ')'){
				while(!_operator.empty()){
					if(_operator.top() == '('){
						_operator.pop();
						break;
					}
					postorder.push_back(_operator.top());
					postorder.push_back(' ');
					_operator.pop();
				}
			}
			else{
				while(!_operator.empty()){
					int x = getIndex(_operator.top());
					int y = getIndex(*i);
					if( precede[x][y] >=0 ){
						postorder.push_back(_operator.top());
						postorder.push_back(' ');
						_operator.pop();
					}
					else
						break;
				}
				_operator.push(*i);
			}
		}
	}
	if(!_operator.empty()){
		if(!postorder.empty() && postorder.back()!=' '){
			postorder.push_back(' ');
		}
		postorder.push_back(_operator.top());
		postorder.push_back(' ');
		_operator.pop();
	}
}

bool isOperator(const char check){
	unsigned int loc = supportedOperator.find(check, 0);
	return loc == string::npos ? false : true;
}

int getIndex(const char src){
	switch(src){
		case '+': return 0;
		case '-': return 1;
		case '*': return 2;
		case '/': return 3;
		case '(': return 4;
		case ')': return 5;
	}
}

int calc(const vector<char>& postorder){
	stack<int> interRes;
	int operand;
	vector<char>::const_iterator i;
	for(i=postorder.begin(); i!=postorder.end(); ++i){
		if( isOperator(*i) ){
			int temp=0;
			switch(*i){
			case '+':
				temp = interRes.top();
				interRes.pop();
				temp += interRes.top();
				interRes.pop();
				interRes.push(temp);
				break;
			case '-':
				temp = interRes.top();
				interRes.pop();
				temp = interRes.top() - temp;
				interRes.pop();
				interRes.push(temp);
				break;
			case '*':
				temp = interRes.top();
				interRes.pop();
				temp *= interRes.top();
				interRes.pop();
				interRes.push(temp);
				break;
			case '/':
				temp = interRes.top();
				interRes.pop();
				temp = interRes.top() / temp;
				interRes.pop();
				interRes.push(temp);
				break;
			}
		}
		else if( isdigit(*i) ){
			interRes.push( calcOperand(postorder, i) );
		}
		//skip space between operators
	}
	return interRes.top();
}

int calcOperand(const vector<char>& postorder, vector<char>::const_iterator& i){
	stack<int> temp;
	while(*i != ' '){
		temp.push( *i-'0' );
		++i;
	}
	double bit=0;
	int res=0;
	while(!temp.empty()){
		res += temp.top()*pow(10.0, bit);
		temp.pop();
		bit++;
	}
	return res;
}</pre>
</div>
试试其它关键字
　顺序栈　
同语言下
可能有用的
Chenyz贡献的其它代码(1)
.用顺序栈计算只含加减乘除和括号的表达式