1222. 계산기1

[ramge132]

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AZC_w6Z6yygDFAQW&contestProbId=AV14mbSaAEwCFAYD&probBoxId=AZDJUP6q-fcDFAVs&type=PROBLEM&problemBoxTitle=2d_practice&problemBoxCnt=3

후위표기식 읽는 법

왼쪽에서 부터 순차적으로 읽기 시작한다. 피연산자(숫자)는 일단 지나치고, 연산자(+-*/)가 나오게 되면, 연산자 앞쪽 두 개의 숫자로 연산을 진행한다.

• 예제) 4 7 2 + *

1. 왼쪽부터 순차적으로 읽으면서 연산자를 찾는다.
2. +연산자를 찾았다. +연산자를 기준으로 앞쪽 두개의 피연산자 7, 2 를 더한다.
3. 연산을 진행하고 나면 연산된 값을 적어둔다. 4 9 *
4. 다시 순차적으로 연산자를 찾는다.
5. *연산자를 찾았다. 앞쪽 두개의 피연산자를 이용하여 연산을 진행한다.
6. 연산결과는 36

[seokbangguri]

from collections import deque

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    input_length = int(input())

    expression = deque()
    formula = list(input())
    expression.extend(formula)

    rear_marking_formula = []
    temp_value = ''

    while len(expression) > 0:
        if expression[0] != '+':
            rear_marking_formula += expression.popleft()
            if temp_value != '':
                rear_marking_formula.append(temp_value)
                temp_value = ''
        else:
            temp_value = expression.popleft()

    # 후위 표기법 변환 결과
    # print(''.join(rear_marking_formula))

    temp_list = []

    for i in rear_marking_formula:
        if i != '+':
            temp_list.append(i)
        else:
            temp_list.append(int(temp_list.pop()) + int(temp_list.pop()))

    print(f'#{test_case} {temp_list[0]}')
    # ///////////////////////////////////////////////////////////////////////////////////

[ramge132]

# 알고리즘 분류: 스택, 구현
# 시간 복잡도: O(N)
# 시간 복잡도 설명:
# 중위 표기식을 후위 표기식으로 변환하는 과정에서 각 문자를 한 번씩 순회, O(N)
# 후위 표기식을 계산하는 과정에서 각 문자를 한 번씩 순회, O(N)
# 따라서 전체 시간 복잡도는 O(N)

# 만약 `1+2+3+4+5` 일 경우
# `output`을 `12+3+4+5+`로 만들기 위한 함수
def to_postfix(expression):
    stack = []  # 연산자를 저장할 스택
    output = []  # 최종 후위 표기식을 저장할 리스트

    for char in expression:  # 입력 문자열을 한 문자씩 순회
        if char.isdigit():  # 문자가 숫자인 경우
            output.append(char)  # 바로 출력 리스트에 추가
        elif char == '+':  # 문자가 '+' 연산자인 경우
            while stack and stack[-1] == '+':  # 스택이 비어 있지 않고, 스택의 top에 있는 연산자가 '+'인 동안 반복
                output.append(stack.pop())  # 스택의 연산자를 출력 리스트에 추가
            stack.append(char)  # 현재 '+' 연산자를 스택에 추가

    while stack:  # 스택에 남아 있는 모든 연산자를 출력 리스트에 추가
        output.append(stack.pop())

    return ''.join(output)  # 출력 리스트를 문자열로 변환하여 반환

def evaluate_postfix(expression):
    stack = []  # 피연산자를 저장할 스택

    for char in expression:  # 후위 표기식을 한 문자씩 순회
        if char.isdigit():  # 문자가 숫자인 경우
            stack.append(int(char))  # 스택에 숫자로 변환하여 추가
        elif char == '+':  # 문자가 '+' 연산자인 경우
            operand2 = stack.pop()  # 스택에서 두 번째 피연산자 추출
            operand1 = stack.pop()  # 스택에서 첫 번째 피연산자 추출
            result = operand1 + operand2  # 두 피연산자를 더함
            stack.append(result)  # 결과를 스택에 추가

    return stack[0]  # 최종 결과 반환

# 사용자 입력 받기
num_tests = 10  # 테스트 케이스의 수

for i in range(num_tests):
    _ = input()  # 문자열 계산식의 길이 입력 (사용하지 않음)
    test_case = input().strip()  # 문자열 계산식 입력
    postfix_expression = to_postfix(test_case)  # 중위 표기식을 후위 표기식으로 변환
    result = evaluate_postfix(postfix_expression)  # 후위 표기식을 계산
    print(f"#{i + 1} {result}")  # 결과를 테스트 케이스 번호와 함께 출력

[ImJongHoon]

import sys
sys.stdin = open("input.txt", "r")

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    num = input()
    infix = input()
    stack = []

    for element in infix:
        if not stack: #스택이 비었으면
            stack.append(element)
        elif stack[-1] == "+":
            operand = stack.pop()
            operator = stack.pop()

            stack.append(str(int(operator) + int(element)))
        else:
            stack.append(element)

    print(f"#{test_case} {stack.pop()}")

[taromilktea00]

'''
def postfix(equation):
    stack = []
    res = []
    for i in range(s_len):
        if equation[i] == '+':
            if stack:
                res.append(stack.pop())
            stack.append('+')
        else:
            res.append(equation[i])

    res.append(stack.pop())
    return res
'''

for t in range(1,11):

    s_len = int(input())
    s = list(map(int, input().split('+')))

    stack = []
    res = 0
    for i in range(len(s)):
        res += s[i]

    print(f'#{t} {res}')