栈的应用——后缀表达式的转化以及计算

后缀表达式的转化

将算术表达式存放在一个字符串中，之后从字符串的第一个字符开始读取。

1. 若是数字，则直接进行输出；
2. 若是左括号，则将其压入栈中；
3. 若是右括号，则进行弹出并输出，直至找到左括号，左括号弹出但不进行输出，若无法找到左括号则证明有错误，输出wrong并停止执行程序；
4. 若是操作符号，则与栈顶所存放的符号比较优先级，若栈为空或优先于栈顶存放的符号，则压入栈中，否则进行弹出操作直至栈为空或者不再优先于栈顶存放的符号时停止，并将该符号压入栈中。在最后将栈中存放的标点符号全部弹出并输出。：

//规定优先级
int priority(char c){//判断优先级 
	if(c=='+' or c=='-') return 2;
	else if(c=='*' or c=='/') return 3;
	else if(c=='(') return 1;
}

//转化为后缀表达式

stringstream ss;
	for (int i=0;i<a.size();i++){
		if(a[i]==' '){
			continue;
		}
		if(isdigit(a[i])){//数字直接输出 
			ss<<a[i]<<" ";
		}
		else{
			int score=priority(a[i]);
			if(a[i]=='('){
				s1.push(a[i]); 
			}
			else if(a[i]==')'){
				while(s1.topValue()!='(' && s1.topValue()!=0){
					ss<<s1.topValue()<<" ";
					s1.pop();
				}
				if(s1.topValue() =='(') s1.pop() ;
				else if(s1.topValue() == 0){
					ss<<"wrong"<<endl;
					return 0;
				}
			}
			else if(s1.topValue()==0 || score>priority(s1.topValue())) s1.push(a[i]);
			else {
				while(s1.topValue()!=0 or score<=priority(s1.topValue() )){
					ss<<s1.pop()<<" " ;
				}
				s1.push(a[i]);
			}

		}
	}
		while(s1.topValue() !=0){
			ss<<s1.pop()<<" ";
		}
	cout<<ss.str()<<endl;

后缀表达式的计算

同样，从字符串的第一个字符开始进行处理，

1. 若为空格，则进行判断，若是数字，即is0函数为真或者n不为0则将这个数字压入栈中并跳过此次循环；
2. 若是数字，则将其放到n中，并且将is0置为真；
3. 若是标点符号，则弹出两个数字并进行相应操作，并将结果压入栈中

最后栈中只剩下一个数字，即为结果，若小于或大于一个数字均为错误，进行输出。若是数字，则将其放到n中，并且将is0置为真；

int sum(string exp){
	AStack<int> num;
	int n=0,t1,t2;
	bool is0=false;
	for(int i=0;i<exp.size();i++){
		if(exp[i]==' '){
			if(n!=0||is0){
				num.push(n);
				n=0; 
				is0=false;
			}
		continue;
		}
		if(isdigit(exp[i])){
			n*=10;
			n+=(exp[i]-'0');
			is0=true;
		}
		else{
			if(num.length()<2){
				cout<<"wrong"<<endl;
				return 0;
			}
			t1=num.pop() ;
			t2=num.pop() ;
			if(exp[i]=='+'){
				t2+=t1;
			}
			else if(exp[i]=='-'){
				t2-=t1;
			}
			else if(exp[i]=='*'){
				t2*=t1;
			}
			else if(exp[i]=='/'){
				t2/=t1;
			}
			num.push(t2); 
		}
	}
	if(num.length()!=1 )cout<<"wrong"<<endl;
	return num.topValue() ;
}

测试