入栈出栈程序

栈（Stack）是计算机科学中的一种数据结构，该数据结构能够保存一系列数据，在该数据结构中，数据的存储和删除是按照特定顺序进行的。栈遵循LIFO（Last in First out）的规则，也就是说，后进入的元素先被处理，先入栈的元素则最后被处理。在计算机领域，栈的一个常见应用是在编程语言中的调用堆栈。在本文中，我们将通过一些示例代码，来演示如何编写一个入栈出栈程序。

栈的基本操作

在编写一个栈程序时，需要实现基本的栈操作，包括入栈、出栈、获取栈顶元素和确定栈是否为空。以下是这些操作的示例代码：

```python

# 定义栈类

class Stack:

# 初始化

def __init__(self):

self.items = []

# 判断栈是否为空

def is_empty(self):

return self.items == []

# 入栈

def push(self, item):

self.items.append(item)

# 出栈

def pop(self):

return self.items.pop()

# 获取栈顶元素

def peek(self):

return self.items[len(self.items)-1]

# 获取栈中元素数量

def size(self):

return len(self.items)

```

在本示例代码中，我们定义了一个栈类，并实现了其各个操作。初始化时，栈是空的。入栈操作通过将元素添加到栈中，出栈操作通过弹出栈顶元素实现，获取栈顶元素的操作则是返回最后一个元素。在此基础上，我们还添加了获取栈中元素数量的操作。

栈的应用

除了作为编程调用堆栈的基本结构外，栈还具有广泛的应用。以下是一些常见的栈应用：

1.括号匹配

例如，在编写JavaScript代码时，括号是非常常见的符号。在语法错误出现时，错误通常是由于括号不匹配而引起的。因此，可以使用栈来检查括号是否匹配。以下是一个示例代码：

```python

def check_parentheses(string):

stack = Stack()

for char in string:

if char in "([{":

stack.push(char)

elif char in ")]}":

if stack.is_empty():

return False

elif match(stack.peek(), char):

stack.pop()

else:

return False

return stack.is_empty()

def match(open, close):

opens = "([{"

closes = ")]}"

return opens.index(open) == closes.index(close)

```

在本代码中，我们首先创建了一个名为`stack`的栈对象，然后遍历给定的字符串。如果遇到了开放的括号，那么该括号将被推入栈中，表示嵌套关系开始。当遇到闭合的括号时，我们将检查栈是否为空，并且该括号是否与栈顶括号匹配。如果是，则将栈顶弹出，并继续遍历字符串。如果不是，则说明字符串不符合括号匹配规则。

2.逆波兰表示法

逆波兰表示法是数学中的一种表示方式，它将运算符写在数字之后，而不是中间。例如，`3 + 4`在逆波兰表示法中为`3 4 +`。这种表示法的优点是它不需要括号来指定操作的优先级。下面是一个基于栈的逆波兰表示法计算器的示例代码：

```python

def calculate(string):

stack = Stack()

tokens = string.split()

operators = set(["+", "-", "*", "/"])

for token in tokens:

if token not in operators:

stack.push(int(token))

else:

right_operand = stack.pop()

left_operand = stack.pop()

if token == "+":

result = left_operand + right_operand

elif token == "-":

result = left_operand - right_operand

elif token == "*":

result = left_operand * right_operand

else:

result = left_operand / right_operand

stack.push(result)

return stack.pop()

```

在本代码中，我们首先创建了一个名为`stack`的栈对象和一个名为`operators`的集合。我们遍历给定的字符串，并将每个token解析为数字和运算符。如果我们遇到一个数字，则将该数字推入到栈中；否则，我们弹出右操作数和左操作数，并计算它们的结果。最后，我们将结果压入栈中，并继续遍历字符串。当遍历结束时，我们弹出栈中唯一剩下的元素，这就是我们的结果。

3.表达式转换

在编写和优化编译器时，表达式的转换是非常常见的任务。常见的转换任务包括将中缀表示法转换为逆波兰表示法或后缀表示法转换为中缀表示法。以下是一个中缀转后缀转换器的示例代码：

```python

def infix_to_postfix(string):

stack = Stack()

tokens = string.split()

output = []

operators = {"+": 1, "-": 1, "*": 2, "/": 2}

for token in tokens:

if token.isdigit():

output.append(token)

elif token in operators:

while not stack.is_empty() and stack.peek() != "(" and operators[stack.peek()] >= operators[token]:

output.append(stack.pop())

stack.push(token)

elif token == "(":

stack.push(token)

elif token == ")":

while stack.peek() != "(":

output.append(stack.pop())

stack.pop()

while not stack.is_empty():

output.append(stack.pop())

return " ".join(output)

```

在本示例代码中，我们首先创建了一个名为`stack`的栈对象和一个名为`operators`的字典，该字典包含每个运算符及其优先级的信息。我们遍历给定的字符串，并将每个token解析为数字、运算符或括号。如果我们遇到一个数字，则将该数字推入输出列表中；如果我们遇到一个运算符，则将栈中的运算符弹出，并将它们推入输出列表中，直到栈顶运算符的优先级低于token的优先级，然后将token推入栈中；如果我们碰到一个左括号，则将其推入栈中；如果我们碰到一个右括号，则将栈中的运算符弹出，并将它们推入输出列表中，直到栈顶是左括号。最后，我们将剩余的运算符从栈中弹出，并将它们推入输出列表中。