栈是一种特殊的线性表，只能在一端进行操作；
往栈中添加元素，一般叫做push，入栈；
移除元素，一般叫做pop，出栈（只能移除栈顶元素，也就是后进先出）；
下面通过一个简单的例子，认识一下栈的用处
/*
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
*/
#include "string"
#include "set"
#include "stack"
class _20_有效的括号 {
public:
bool isValid(std::string s) {
if (s.length() < 1) return true;
char left[] = {'(', '{', '['};
char right[] = {')', '}', ']'};
int size_left = sizeof(left) / sizeof(char);
int size_right = sizeof(right) / sizeof(char);
std::stack<int> left_stack{};
// std::vector<int> left_arr(0);//存储符合所对应的index，便于比较左 右符号是否匹配
for (char c : s) {
char* res_left = std::find(left, left+size_left, c);
if (res_left != left+size_left) {//判断是否是左符号
int value = res_left - left + 1;
// left_arr.push_back(value);
left_stack.push(value);
} else {
char* res_right = std::find(right, right + size_right, c);
if (res_right != right+size_right) {
if (left_stack.empty()) return false;
// if (left_arr.empty()) return false;
int last_left_value = left_stack.top();
// int last_left_value = left_arr.back();
int value = res_right-right+1;
if (last_left_value == value) {
// left_arr.pop_back();
left_stack.pop();
} else {
return false;
}
}
}
}
// return left_arr.empty();
return left_stack.empty();
}
};
前缀表达式
前缀表达式是一种没有括号的算术表达式与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。
求值方法
对前缀表达式求值，要从右至左扫描表达式，首先从右边第一个字符开始判断，若当前字符是数字则一直到数字串的末尾再记录下来，若为[运算符]，则将右边离得最近的两个“数字串”作相应运算，然后以此作为一个新的“数字串”并记录下来；扫描到表达式最左端时扫描结束，最后运算的值即为[表达式]的值。
例如：对前缀表达式“- 1 + 2 3”求值，扫描到3时，记录下这个数字串，扫描到2时，记录下这个数字串，当扫描到+时，将+右移做相邻两数字串的运算符，记为2+3，结果为5，记录下5这个新数字串，然后继续向左扫描，扫描到1时，记录下这个数字串，扫描到-时，将-右移做相邻两数字串的运算符，记为1-5，结果为-4，此时关于这个表达式的全部运算已完成，故表达式的值为-4。
转换方式
前缀表达式转换.png
后缀表达式
后缀表达式（也称为[逆波兰表达式]）是一种数学表达式的表示方法，其中操作符位于操作数的后面。这种表示法消除了括号，并且在计算机科学和计算中非常有用，因为它更容易计算和解析。
求值方法
先从左到右依次入栈，当是数字的时候直接入栈
当是运算符号的时候，就将栈的最上面两个数拿出进行运算 后 再将结果进栈 记住（栈顶元素永远在运算符号的右边）
后缀表达式：9 3 1 - 3 x + 10 2 ÷ +
第一步从左到右依次入栈 9 3 1
现在栈从上到下1 3 9 进入符号 - 将1和3 拿出 3-1 =2
（栈顶元素永远在运算符号的右边）
然后再把2进栈
现在栈从上到下是 2 9
再进入3
现在栈从上到下是 3 2 9
再运算符号 x 拿出 2x3 =6 再进栈
现在栈从上到下是 6 9
在运算+ 6+9=15
现在栈从上到下是 15
进入 10 2
现在栈从上到下是 2 10 15
运算 ÷ 10÷2=5 5 进栈
现在栈从上到下是 5 15
最后运算+ 15+5
得20
后缀表达式：9 3 1 - 3 x + 10 2 ÷ + =20
转换方式
创建栈S1、S2，后缀表达式从左到右遍历，
1，是数字直接入栈S1，
2，是任何运算符号
- ( ，直接入栈S2
- 优先级高于S2栈顶元素，直接入栈S2
- 优先级低于或等于S2栈顶元素，则将栈顶元素出栈并入栈到S1，直至满足条件后入栈S2
- )，将与( 之间的元素都出栈并入栈到S1
中缀表达式 9+（3-1）x3+10÷2
从左到右遍历
9 入栈S1
当前S1为 9
+ 入栈S2（目前栈空，栈空就进栈）
（ 入栈S2
目前栈S2为(左右边为栈顶)： + (
3入栈S1
当前S1为 9 3
- 入栈S2
目前栈S2: + ( -
[中缀表达式 9+（3-1）x3+10÷2]
1 入栈S1
当前栈S1为 9 3 1
）右括号 遇到右括号 输出栈顶元素 并抵消左括号
写上 -
当前栈S1为 9 3 1 -
当前栈S2从上到下 +
[中缀表达式 9+（3-1）x3+10÷2]
x 优先级高于+ 直接入栈S2
3直接入栈S1
当前栈S1: 9 3 1 - 3
当前栈S2: + x
!! 接下来 + 判断优先级, +优先级小于x, x 出栈S2并入栈S1
判断优先级 + 和+ 相同, 属于不高于, + 出栈S2，并入栈S1
当前栈S1: 9 3 1 - 3 x +
当前栈S2: +
再后面 10 入栈S1
÷ 判断优先级 高于+ 进栈S2
2 入栈S1
当前栈S1：9 3 1 - 3 x + 10 2
当前栈S2：+ ÷
由于已经没有符号和数字了
栈S2内依次出栈并入栈S1
最后得出S1: 9 3 1 - 3 x + 10 2 ÷ +
网友评论