掌握栈的基本操作算法的实现,包括栈初始化、进栈、出栈、取栈顶元素,掌握利用栈实现中缀表达式求值的算法C++
时间: 2024-12-30 15:40:19 浏览: 12
栈是一种线性的数据结构,它的基本操作包括初始化、压入(进栈)、弹出(出栈)以及访问顶部元素(获取栈顶元素)。在C++中,我们可以使用数组或动态数据结构如std::stack来实现。
1. **栈的初始化**:
- 如果使用数组,需要预先定义数组大小并初始化所有元素为空或特定值(例如0或nullptr)。
- 使用`std::stack`的话,可以直接创建一个空栈:
```cpp
std::stack<int> myStack;
```
2. **进栈(压栈)**:
- 数组实现:`arr[top++] = value;`
- `std::stack`:`myStack.push(value);`
3. **出栈(弹栈)**:
- 数组实现:`top--; return arr[top];`
- `std::stack`:`return myStack.top(); myStack.pop();`
4. **取栈顶元素**:
- 数组实现:`return arr[top];`
- `std::stack`:`return myStack.top();`(但这不会改变栈的状态)
5. **中缀表达式求值**:
- 利用栈实现算法称为“逆波兰表示”(Reverse Polish Notation, RPN),也叫后缀表达式。先将运算符按优先级顺序压栈,遇到数字则将其压栈,当遇到左括号时,从栈中弹出运算符直到遇到右括号。最终栈顶剩下的就是计算结果。
```cpp
int evalInfix(std::string expr) {
std::stack<std::pair<char, int>> ops;
for (char c : expr) {
if (isdigit(c)) { // 遇到数字直接压栈
ops.push({c - '0', 1});
} else if (c == '+' || c == '-') { // 遇到运算符
while (!ops.empty() && precedence(ops.top().first) >= precedence(c)) {
// 弹出运算符,进行计算并再次压栈结果
ops.pop();
}
ops.push({c, 0}); // 0 表示暂时存放运算符
} else if (c == '(') { // 遇到左括号,推入栈
ops.push({c, 0});
} else if (c == ')') { // 遇到右括号,直至找到左括号
while (ops.top().first != '(') {
// 结果累加运算
result += calculate(ops.top());
ops.pop();
}
ops.pop(); // 出栈左括号
}
}
while (!ops.empty()) {
result += calculate(ops.top());
ops.pop();
}
return result;
}
```
阅读全文