本篇记录关于栈的经典问题。

括号匹配问题

这也是一个经典的问题，一句话就是判断字符串中圆括号、中括号、花括号是否成对出现。
算法基本思想：
第一步：遇到{,[,(，将它压入栈中。
第二步：遇到},},),将其与栈中元素比较，看是否成对出现。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <string>
#include <stack>
using namespace std;
//判断字符串中括号是否匹配。
bool isValidParentheses(string str)
{
	stack<char> st;
	char temp;
    //一次遍历整个字符串
	for (int i = 0; i < str.length(); i++)
	{
    //栈空不可对栈有操作，否则会引发segmentation fault
		if(!st.empty())
			temp=st.top();
		if(str[i]=='{'||str[i]=='('||str[i]=='[')
			st.push(str[i]);
		else if(str[i]=='}')
		{
			if(temp=='{'&&(!st.empty()))
				st.pop();
			else
				return false;
		}
		else if(str[i]==']')
		{
			if(temp=='['&&(!st.empty()))
			{
				st.pop();
			}
			else
				return false;
		}
		else if(str[i]==')')
		{
			if(temp=='('&&(!st.empty()))
				st.pop();
			else
				return false;
		}
	}
	if(st.empty())
		return true;
	else
		return false;
}
int main()
{
	string str="45)[s5s]{}";
	cout<<isValidParentheses(str)<<endl;
	return 0;
}

求解后缀表达式

一般指的是中缀表达式转成后缀表达式，因为后缀表达式可以利用栈来进行四则运算。具体的思想可以参考利用栈将中缀表达式转换成后缀表达式,这里贴出具体的代码实现 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
vector<string> InfixToPostfix(vector<string> infix)
{
	vector<string> postfix;//后缀表达式
	stack<string> mark;//符号栈
	//优先级
	map<string,int> priority;
    priority["+"] = 0;
    priority["-"] = 0;
    priority["*"] = 1;
    priority["/"] = 1;
    priority["("] = 2;
    priority[")"] = -1;
    string current;
    string top;
    for (int i = 0; i < infix.size(); i++)
    {
    	/* code */
    	current=infix[i];
    	//判断需要入栈的运算符
  	if(current=="+"||current=="-"||current=="*"||current=="/"||current=="(")
    	{
    		//栈空直接入栈
    		if(mark.empty())
    		{
    			mark.push(current);
    		}
    		else
    		{
    			//栈顶元素优先级大于等于current，栈顶元素出栈,否则current入栈
    			while(!mark.empty())
    			{
    				top=mark.top();
    				if(priority[top]>=priority[current])
    				{
    					if(top=="(")
    					{
    						mark.push(current);
    						break;
    					}
    					else
    					{
    						postfix.push_back(top);
    						mark.pop();
    					}
    				}
    				else
    				{
    					mark.push(current);
    					break;
    				}
    			}
    //由于栈中元素的优先级都比current高，此时栈中元素都被输出，栈为空，current入栈
    			if(mark.empty())
    			{
    				mark.push(current);
    			}
    		}
    	}
    	else if(current==")")
    	{
    		while(!mark.empty())
			{
				top=mark.top();
				if(top!="(")
				{
					postfix.push_back(top);
					mark.pop();
				}
				else
				{
					mark.pop();
					break;
				}
			}
    	}
    	else
    	{
    		postfix.push_back(current);
    	}
    }
    //输出符号栈剩余字符
     while(!mark.empty())
    {
    	top=mark.top();
    	postfix.push_back(top);
    	mark.pop();
    }
    return postfix;
}