570-栈(括号匹配,逆波兰式)

清疚 2022-09-11 13:12 165阅读 0赞

## 括号匹配问题 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]  
**刚开始，出现的都是左括号，然后第一次出现)是和刚才遍历的最后一个比较，以此类推下去。**  
当我们刚开始遍历的时候，要把左括号都存储下来，当我们开始遇见右括号的话，然后把刚才遍历的左括号中从后向前（倒着来）和右括号比对![在这里插入图片描述][5f2e743afcbc457e854dcd8f45feb16e.png]  
**很明显，可以借用栈结构（先入后出，后入先出）**  
我们刚开始遍历，把遇见的左括号都入栈。  
![在这里插入图片描述][141a383ab269467281984c699447cc35.png]  
**现在我们遇见右括号了，然后取出栈顶取元素和这个右括号比对。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]  
**是匹配的。然后继续访问下一个右括号，然后取栈顶元素进行比对。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]  
**以此类推下去。**  
**然后遇见3个右括号，都和栈顶元素相匹配。**  
![在这里插入图片描述][7911c5181f33475f91cadf36a4adc966.png]  
![在这里插入图片描述][9590f53efb2c4dccad42f33287362f1b.png]  
**然后又遇见左括号了，就入栈。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_10_color_FFFFFF_t_70_g_se_x_16]  
**然后又遇见右括号，就取栈顶元素进行比对。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16 1]  
**以此类推下去**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]

#include <iostream>
    #include<string>
    #include<stack>
    using namespace std;
    
    
    class Solution
    {
        
    public:
    	bool isValid(string s)
    	{
        
    		stack<char>cs;
    		for (char ch : s)
    		{
        
    			if (ch == '(' || ch == '[' || ch == '{')
    			{
        
    				cs.push(ch);
    			}
    			else
    			{
        
    				if (cs.empty())
    				{
        
    					return false;
    				}
    				char cmp = cs.top();
    				cs.pop();
    				if (ch == ')' && cmp != '(' || ch == ']' && cmp != '[' || ch == '}' && cmp != '{')
    				{
        
    					return false;
    				}
    			}
    		}
    		return cs.empty();
    	}
    };

## 逆波兰表达式 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]

**遇到数字，直接入栈，遇到运算符，就出栈，因为+是双目运算符，出栈2个元素，计算出1+2=3，然后把3入栈**  
**先出栈的作右操作数，后出栈的作左操作数**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][570a019fbc4944c7a0dfb38f6a79ea05.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**以此类推，最后栈里面剩下的那个数字就是逆波兰表达式对应的中缀表达式的结果了。**

![在这里插入图片描述][55d41a721a3f433c9c8e2143f4f8d728.png]  
![在这里插入图片描述][2e7675aaf74548828dc10cd94791b6ea.png]  
3x7=21  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16]**最后的结果就是21**

![在这里插入图片描述][f0fadf9b090c403a99a0a073041f70c7.png]

## 逆波兰表达式求解代码实现 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

#include <iostream>
    #include<string>
    #include<stack>
    #include<vector>
    using namespace std;
    
    
    class Solution
    {
        
    public:
    	int calc(int left, int right, char sign)
    	{
        
    		switch (sign)
    		{
        
    		case'+':return left + right;
    		case'-':return left - right;
    		case'*':return left * right;
    		case'/':return left / right;
    		}
    		throw "";
    	}
    	bool evalRPN(vector<string>& tokens)
    	{
        
    		stack<int>intStack;
    		for (string& str : tokens)
    		{
        
    			if (str.size() == 1 && (str[0] == '+' || str[0] == '-'
    				|| str[0] == '*' || str[0] == '/'))
    			{
        
    				int right = intStack.top();
    				intStack.pop();
    
    				int left = intStack.top();
    				intStack.pop();
    				
    				intStack.push(calc(left, right, str[0]));
    			}
    			else//遇到数字，直接入栈
    			{
        
    				//string->int,使用stoi stol stof
    				//itn -> string，使用to_string
    				intStack.push(stoi(str));
    			}
    		}
    		return intStack.top();
    	}
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/03cbe96f795a447895b1caf25bff8a8b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/26d4b26b45e849b38d16d2161fa70137.png
[5f2e743afcbc457e854dcd8f45feb16e.png]: /images/20220828/b7fcecb53d1f4caa85960d9753033e08.png
[141a383ab269467281984c699447cc35.png]: /images/20220828/4e9ef1dfffe8477cbf1feec106a6900e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b10f81441e9342c8a4bf9efbf05458e5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ab37493e86224ea2beac152c9da14797.png
[7911c5181f33475f91cadf36a4adc966.png]: /images/20220828/c5efe2eae913412fb90f76c6a5f2fdb3.png
[9590f53efb2c4dccad42f33287362f1b.png]: /images/20220828/1b6890cec2b34d35ba969a531fff387c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/40a547fc915a4969a0cbc7f0ed19c283.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/8547794bfea645009b12a3b6a949f828.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/885d03f076ff494c8453b3dada7ff1d9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/f39ba5b8ce9f4c08b17c5197a37d941b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/6710b1a2ebe745f99fd848c9eb09a375.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/b773305cb222442fb4c926a41da7e2da.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/661fea579a434e19868681dbb39426b3.png
[570a019fbc4944c7a0dfb38f6a79ea05.png]: /images/20220828/7fecda30a3d9469b85ab610cbeec9d9e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/7ca03894df1b42558c22f3871bf2e0e3.png
[55d41a721a3f433c9c8e2143f4f8d728.png]: /images/20220828/f0387784c0fd4ed3a06a61adde8fab20.png
[2e7675aaf74548828dc10cd94791b6ea.png]: /images/20220828/2760bc1831fe421c9a8c8d2093f8a0ea.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/601ca503438048b6b97ca0d11ea42cfd.png
[f0fadf9b090c403a99a0a073041f70c7.png]: /images/20220828/53e965f3119d4266aef3cfd8290524a3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/29eb734f275b4cb5b9358ef565f78ead.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/e5c578eac4aa44438cee3902cbdac4bb.png