1 栈的应用 7题

sy293: 栈的操作序列简单

https://sunnywhy.com/sfbj/7/1/293

现有一个空栈s，按顺序执行n个操作序列，每个操作是下面的两种之一：

往s中压入一个正整数k
弹出的栈顶元素，同时将其输出

输入

第一行一个整数 n（ $1 \leq n \leq 100$ ），表示操作序列的个数；

接下来行，每行一个操作序列，格式为以下两种之一，分别对应入栈和出栈的操作，其中push k表示需要将整数k（ $1 \leq k \leq 100$ ）压入栈，而pop表示需要弹出栈顶元素：

push k
pop

输出

输出多行，每次弹出时输出一行，表示弹出的栈顶元素。如果无法弹出栈顶元素，那么输出-1。

样例1

输入

8
push 2
pop
pop
push 5
push 3
push 6
pop
pop

输出

解释

初始时栈为空，即[]。接下来进行以下8个操作：

push 2：将2入栈，此时栈为[2]；
pop：栈顶元素为2，因此输出2，弹出后栈为[]；
pop：由于栈空，无法弹出元素，因此输出-1；
push 5：将5入栈，此时栈为[5]；
push 3：将3入栈，此时栈为[5,3]；
push 6：将6入栈，此时栈为[5,3,6]；
pop：栈顶元素为6，因此输出6，弹出后栈为[5,3]；
pop：栈顶元素为3，因此输出3，弹出后栈为[5]。

The user is asking for a Python program that simulates a stack with push and pop operations. The program should read a sequence of operations from the input, perform these operations on the stack, and print the result of each pop operation. If a pop operation is attempted on an empty stack, the program should print -1.

Here is a Python program that accomplishes this:

python

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append(x)

    def pop(self):
        return self.stack.pop() if self.stack else -1

def main():
    n = int(input().strip())
    stack = Stack()
    for _ in range(n):
        operation = input().strip().split()
        if operation[0] == 'push':
            stack.push(int(operation[1]))
        elif operation[0] == 'pop':
            print(stack.pop())

if __name__ == "__main__":
    main()

In this program, we define a Stack class with push and pop methods. The push method appends an element to the end of the stack, and the pop method removes and returns the last element of the stack, or -1 if the stack is empty. In the main function, we read the number of operations from the input, create a Stack object, and perform the operations on the stack. If the operation is a pop, we print the result.

sy294: 合法的出栈序列简单

https://sunnywhy.com/sfbj/7/1/294

现有一个空栈s和一个正整数n，将1,2,3,...,n依次入栈，期间任意时刻出栈。然后给定一个出栈序列，问其是否是一个合法的出栈序列。

输入

第一行一个整数n（ $1 \leq n \leq 100$ ），表示需要入栈的整数个数；

第二行为[1,n]的一个排列，表示一个出栈序列，整数间用空格隔开。

输出

如果出栈序列合法，那么输出Yes，否则输出No。

样例1

输入

4
3 2 4 1

输出

Yes

解释

初始时栈为空，即[]。接下来按下面的顺序执行即可得到出栈序列3 2 4 1：

1入栈，此时栈为[1]；
2入栈，此时栈为[1,2]；
3入栈，此时栈为[1,2,3]；
3出栈，此时栈为[1,2]；
2出栈，此时栈为[1]；
4入栈，此时栈为[1,4]；
4出栈，此时栈为[1]；
1出栈，此时栈为[]。

样例2

输入

4
3 4 1 2

输出

No

解释

无法达成出栈序列3 4 1 2

The user is asking for a Python program that checks if a given sequence of numbers can be a valid sequence of popped elements from a stack. The stack initially contains a sequence of integers from 1 to n, and the program should simulate pushing these integers onto the stack and popping them off in the order given by the input sequence. If it's possible to pop off the integers in the given order, the program should print Yes, otherwise it should print No.

Here is a Python program that accomplishes this:

python

def is_valid_sequence(n, sequence):
    stack = []
    j = 0

    for i in range(1, n + 1):
        stack.append(i)
        while stack and stack[-1] == sequence[j]:
            stack.pop()
            j += 1

    return 'Yes' if not stack else 'No'

def main():
    n = int(input().strip())
    sequence = list(map(int, input().strip().split()))
    print(is_valid_sequence(n, sequence))

if __name__ == "__main__":
    main()

In this program, we define a function is_valid_sequence that simulates pushing integers onto a stack and popping them off in the order given by the input sequence. If it's possible to pop off the integers in the given order, the function returns Yes, otherwise it returns No. In the main function, we read the number of integers and the sequence from the input, and print the result of is_valid_sequence.

sy295: 可能的出栈序列中等

https://sunnywhy.com/sfbj/7/1/295

现有一个空栈s和一个正整数n，将1,2,3,...,n依次入栈，期间任意时刻出栈。求所有可能的出栈序列。

输入

一个整数n（ $1 \leq n \leq 8$ ），表示需要入栈的整数个数。

输出

按字典序从小到大的顺序，每行输出一组可能的出栈序列，整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

输出

解释

3 1 2是无法达成的，因为第一个出栈的是3，但此时栈顶为2，不可能把1出栈。

The user is asking for a Python program that generates all possible sequences of popped elements from a stack. The in_stack initially contains a sequence of integers from 1 to n, and the program should simulate pushing these integers onto the stack and popping them off in any order. The program should print all possible sequences of popped elements, sorted in lexicographical order.

Here is a Python program that accomplishes this:

python

def generate_sequences(stack, in_stack, out_stack, output):
    if len(in_stack) == 0 and len(stack) == 0:
        output.append(out_stack)
    if len(in_stack) > 0:
        generate_sequences(stack + [in_stack[0]], in_stack[1:], out_stack, output)
    if len(stack) > 0:
        generate_sequences(stack[:-1], in_stack, out_stack + [stack[-1]], output)

def main():
    n = int(input().strip())
    in_stack = list(range(1, n + 1))
    output = []
    generate_sequences([], in_stack, [], output)
    output.sort()
    for sequence in output:
        print(' '.join(map(str, sequence)))

if __name__ == "__main__":
    main()

In this program, we define a function generate_sequences that recursively simulates pushing integers onto a stack and popping them off in any order, and adds the resulting sequences to the output list. The function is called with an empty stack, the sequence of integers to be pushed onto the stack, an empty output sequence, and an empty output list. In the main function, we read the number of integers from the input, generate all possible sequences of popped elements, sort them in lexicographical order, and print them.

sy296: 后缀表达式-无优先级简单

https://sunnywhy.com/sfbj/7/1/296

给定一个仅由+、-、整数、空格组成的计算式（中缀表达式），将其转换为对应的后缀表达式（即逆波兰表达式）。

输入

一个长度不超过100的字符串，仅由+、-、整数（不小于1且不大于9）、空格组成，其中操作符和操作数之间用空格分隔。数据保证表达式一定合法。

输出

输出对应的后缀表达式，其中操作数和操作符之间用空格隔开，行末不允许有多余的空格。

样例1

输入

3 + 4 - 5

输出

3 4 + 5 -

解释

3 + 4转换为后缀表达式为3 4 +，记为P；

P - 5转换为后缀表达式为P 5 -，展开后即为3 4 + 5 -

The user is asking for a Python program that converts an infix expression to a postfix (Reverse Polish Notation) expression. The program should read an infix expression from the input, convert it to a postfix expression, and print the result.

Here is a Python program that accomplishes this:

python

def infix_to_postfix(infix):
    precedence = {'+': 1, '-': 1}
    stack = []
    postfix = []

    for token in infix:
        if token.isdigit():
            postfix.append(token)
        else:
            while stack and precedence[stack[-1]] >= precedence[token]:
                postfix.append(stack.pop())
            stack.append(token)

    while stack:
        postfix.append(stack.pop())

    return ' '.join(postfix)

def main():
    infix = input().strip().split()
    print(infix_to_postfix(infix))

if __name__ == "__main__":
    main()

In this program, we define a function infix_to_postfix that converts an infix expression to a postfix expression. The function uses a stack to hold operators and a list to hold the postfix expression. For each token in the infix expression, if the token is a digit, it is added to the postfix expression. If the token is an operator, operators are popped from the stack and added to the postfix expression until the stack is empty or the operator at the top of the stack has lower precedence than the current operator. Then the current operator is pushed onto the stack. After all tokens have been processed, any remaining operators are popped from the stack and added to the postfix expression. In the main function, we read the infix expression from the input, convert it to a postfix expression, and print the result.

sy297: 后缀表达式-有优先级中等

https://sunnywhy.com/sfbj/7/1/297

给定一个仅由+、-、*、/、整数、空格组成的计算式（中缀表达式），将其转换为对应的后缀表达式（即逆波兰表达式）。

输入

一个长度不超过100的字符串，仅由+、-、*、/、整数（不小于1且不大于9）、空格组成，其中操作符和操作数之间用空格分隔。数据保证表达式一定合法。

输出

输出对应的后缀表达式，其中操作数和操作符之间用空格隔开，行末不允许有多余的空格。

样例1

输入

3 + 4 * 5

输出

3 4 5 * +

解释

由于乘法的优先级比加法高，因此需要先处理乘号：

4 * 5转换为后缀表达式为4 5 *，记为P；

3 + P转换为后缀表达式为3 P +，展开后即为3 4 5 * +

Here is a Python program that accomplishes this:

python

def infix_to_postfix(infix):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    stack = []
    postfix = []

    for token in infix:
        if token.isdigit():
            postfix.append(token)
        else:
            while stack and precedence[stack[-1]] >= precedence[token]:
                postfix.append(stack.pop())
            stack.append(token)

    while stack:
        postfix.append(stack.pop())

    return ' '.join(postfix)

def main():
    infix = input().strip().split()
    print(infix_to_postfix(infix))

if __name__ == "__main__":
    main()

sy298: 后缀表达式-求值中等

https://sunnywhy.com/sfbj/7/1/298

给定一个仅由+、-、*、/、整数组成的计算式（后缀表达式），计算它的值。

输入

一个长度不超过100的字符串，其中操作符和操作数仅由+、-、*、/、整数（不小于1且不大于9）构成，且操作符和操作数之间用空格分隔。数据确保表达式一定合法，且计算过程的所有结果不会超过。

输出

输出求值结果（保留两位小数精度）。

样例1

输入

3 4 5 * +

输出

23.00

解释

先计算4 5 *，得到20；然后计算3 20 +，得到23

The user is asking for a Python program that evaluates a postfix (Reverse Polish Notation) expression. The program should read a postfix expression from the input, evaluate it, and print the result. The postfix expression can include addition, subtraction, multiplication, and division operators.

Here is a Python program that accomplishes this:

python

def evaluate_postfix(postfix):
    stack = []

    for token in postfix:
        if token.isdigit():
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a / b)

    return round(stack[0], 2)

def main():
    postfix = input().strip().split()
    print("{:.2f}".format(evaluate_postfix(postfix)))

if __name__ == "__main__":
    main()

In this program, we define a function evaluate_postfix that evaluates a postfix expression. The function uses a stack to hold operands. For each token in the postfix expression, if the token is a digit, it is pushed onto the stack. If the token is an operator, two operands are popped from the stack, the operation is performed, and the result is pushed back onto the stack. After all tokens have been processed, the result of the expression is the only element left on the stack. In the main function, we read the postfix expression from the input, evaluate it, and print the result.

sy299: 简单计算器困难

https://sunnywhy.com/sfbj/7/1/299

给定一个仅由+、-、*、/、整数组成的计算式（中缀表达式），计算它的值。

输入

输出

输出求值结果（保留两位小数精度）。

样例1

输入

3 + 4 * 5

输出

23.00

解释

3 + 4 * 5 = 3 + 20 = 23

The user is asking for a Python program that evaluates an infix expression. The program should read an infix expression from the input, convert it to a postfix expression, evaluate it, and print the result. The infix expression can include addition, subtraction, multiplication, and division operators.

Here is a Python program that accomplishes this:

python

def infix_to_postfix(infix):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    stack = []
    postfix = []

    for token in infix:
        if token.isdigit():
            postfix.append(token)
        else:
            while stack and precedence[stack[-1]] >= precedence[token]:
                postfix.append(stack.pop())
            stack.append(token)

    while stack:
        postfix.append(stack.pop())

    return postfix

def evaluate_postfix(postfix):
    stack = []

    for token in postfix:
        if token.isdigit():
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a / b)

    return round(stack[0], 2)

def main():
    infix = input().strip().split()
    postfix = infix_to_postfix(infix)
    print("{:.2f}".format(evaluate_postfix(postfix)))

if __name__ == "__main__":
    main()

In this program, we first convert the infix expression to a postfix expression using the infix_to_postfix function. Then we evaluate the postfix expression using the evaluate_postfix function. The main function reads the infix expression from the input, converts it to a postfix expression, evaluates it, and prints the result.

1 栈的应用 7题 ​

sy293: 栈的操作序列 简单 ​

sy294: 合法的出栈序列 简单 ​

sy295: 可能的出栈序列 中等 ​

sy296: 后缀表达式-无优先级 简单 ​

sy297: 后缀表达式-有优先级 中等 ​

sy298: 后缀表达式-求值 中等 ​

sy299: 简单计算器 困难 ​

1 栈的应用 7题

sy293: 栈的操作序列简单

sy294: 合法的出栈序列简单

sy295: 可能的出栈序列中等

sy296: 后缀表达式-无优先级简单

sy297: 后缀表达式-有优先级中等

sy298: 后缀表达式-求值中等

sy299: 简单计算器困难