基本操作

stl中stack出栈，如例：s.pop();注意，出栈操作只是删除栈顶元素，并不返回该元素

运用

任何出栈的元素后面出栈的元素必须满足以下三点，在原序列中相对位置比它小的，对于该元素后面必须是逆序
(2n)!/(n!(n+1)!)为出栈顺序总类数
后缀表达式
后缀表达式又称逆波兰表达式，后缀记法
后缀表达式计算机求值
- 与前缀表达式类似，只是顺序是从左至右：
  - 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
步骤:

题目：

ctguoj
191.2016栈与队_表达式转换 (20分) 
C时间限制：3000 毫秒 |  C内存限制：3000 Kb
题目内容：
 算术表达式有前缀表示法、中缀表示法、后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，
即二元运算符位于两个运算数之间。请设计程序将中缀表达式转换为后缀表达式。
中缀表示：2+3-4
后缀表示：2 3 + 4 -， 符号在两个运算数据的后面。后缀表达有很多好处，例如可以不要括号，见下面
的样例。
 
输入描述
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、/、（、）运算符，以#结束表达式

输出描述
在一行中给出转换后的表达式，要求不同对象（运算数、运算符号）之间以空格分隔

输入样例
2+3*(7-4)#


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

using namespace std;

stack<char> st2; 
stack<char> st;

int compre(char a){
	switch(a){
		case '*':
		case '/':
			return 1;
		default:
			if(!st.empty()){
			char b = st.top();
			if(b == '*'||b == '/') return 0;
			else return 1;
		}
		else{
			return 1;
		}
	}
}
int main(){
	string str;
	cin >> str;
	int i;
	for(i = 0; i < str.size(); i++){
		switch(str[i]){
			case '(':
			case ')': //((2+3)*4-(8+2))/5#
				if(str[i] == '(') st.push(str[i]);
				else{
					if(!st.empty()){
						char a = st.top();
						int c = st.size();
						for(int j = 0; j < c; j++){
						a = st.top();
						if(a != '(') st2.push(a);
						st.pop();
						}	
					}
				}
				break;
			case '*':
			case '/':	
			case '-':
			case '+':
				if(st.empty() || (st.top() == '(') ){
					st.push(str[i]);
				} 
				else{
					if(compre(str[i])) st.push(str[i]);
					else{
						int a = st.top();
						st2.push(a);
						st.pop();
						if(compre(str[i])) st.push(str[i]);
					}
				}
				break;
			case '#':
				break;
			default:
				st2.push(str[i]);
		}
	}
	int size1 = st.size();
	for(i = 0; i < size1; i++){
		st2.push( st.top() );
		st.pop();
	}
	string str2;
	int size2 = st2.size();
	for(i = size2-1; i >= 0; i--){
		if(!st2.empty()){
			str2 += st2.top();
			st2.pop();
		}
	}
	for(i = str2.length()-1; i >= 0; i--){          
		if(str2[i] != '(') cout << str2[i] << " "; 
		else continue;
}
//((2+3)*4-(8+2))/5#
	return 0;
}

括号匹配

检验表达式中左右括号(多种&&嵌套)是否可以对应匹配

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

using namespace std;

int march(char a, char b){
	switch(a){
		case '(':
			if(b == ')')
				return 1;
			else
				return 0;
			break;
				
		case '[':
			if(b == ']')
				return 1;
			else
				return 0;
			break;
		case '{':
			if(b == '}')
				return 1;
			else
				return 0;
			break;
	}	
}

int main(){
	int k = 0;
	string str;
	stack<char> st;
	cin >> str;
	for(int i = 0; i < str.size()-1; i++){
		switch(str[i]){
			case '(':
			case '[':
			case '{':
			case ')':
			case ']':
			case '}':
				k = 1;
				break;
		}
		if(k == 1)
			break;
	}
	if(k == 0){
		cout << "NO";
		return 0;
	}
	for(int i = 0; i < str.size()-1; i++){
		switch(str[i]){
			case '(':
			case '[':
			case '{':
				st.push(str[i]);
				break;
			case ')':
			case ']':
			case '}':
				if(st.empty()){
					cout << "NO";
					return 0;
				}
				else{
					if( march(str[i], st.top()) ){
						st.pop();
					}
					else{
						cout << "NO";
						return 0;
					}
				}
		}
	}	
	if(st.empty())
		cout << "YES";
	else{
		cout << "NO";
	}
	return 0;
}

资料

博客园