역 폴란드 식 ☆ 알고리즘 과 데이터 구조
5431 단어 python 알고리즘 - 데이터 구조
만약 당신 이 이미 알 고 있 는 두 개의 숫자 를 더 하거나 곱 해 야 한다 면, 코드 로 표현 하 는 것 은 매우 easy 입 니까?그리고 만약 에 유사 한
1+1 기호 두 개의 숫자 로 구 성 된 문자열 을 제시 하면 그 결 과 를 요구 할 수 있 고 split() 함수 로 문자열 을 나 누 어 계산 할 수 있 으 며 난이도 가 별로 없다.한 단계 더 업그레이드 하 겠 습 니 다. 이 문자열 이 두 개의 숫자 와 하나의 기호 만 있 는 것 이 아니 라 덧셈 과 괄호 를 포함 하 는 복잡 한 산술 표현 식 입 니까?예 를 들 어 다음 산술 표현 식:
1 + ( 2 - 3 * 4 ) / 5 + 6우 리 는
을 사용 하여 이 산술 표현 식 의 계산 을 완성 할 수 있다.두 개의 스 택 을 만들어 각각 숫자 와 기 호 를 저장 한 다음 에 기호 간 의 우선 순위 관 계 를 통 해 이전 기호 가 계산 할 수 있 는 지 여 부 를 판단 합 니 다.구체 적 인 방법 은 글 224. 기본 계산기 ☆ leetcode 에서 상세 하 게 해석 되 었 고 본 고 는 이런 방법 을 반복 적 으로 해석 하지 않 으 며 알 고 싶 은 파트너 는 링크 를 클릭 하여 글 을 볼 수 있다.지금 본문의 주인공 을 내 주세요!
주인공 등장
본문의 주인공 은
이 고 접미사 표현 식 이 라 고도 부른다.후자 라 는 비교적 통속 적 인 이름 은 자신의 의 미 를 명확 하 게 나타 내 는데 계산 하 는 기호 가 계산 해 야 할 두 개의 숫자 뒤에 있다 는 뜻 이다.우리 가 자주 사용 하 는 산술 표현 식 은 접미사 표현 식 으로 계산 기 호 는 두 숫자 사이 에 있다.현실 에 서 는 역 폴란드 식 장면 을 직접 제시 하지 않 았 다. 즉, 접두사 표현 식 을 역 폴란드 식 으로 바 꿔 야 한 다 는 뜻 이다.
우 리 는 위의 예 를 사용 하여 역 폴란드 표현 식 으로 전환 하 는 것 이 어떤 모습 인지 먼저 볼 수 있 습 니 다.
1 2 3 4 * - 5 / + 6 +이: 어떻게 한 거 야
정말 이상 한 문자열 인 데, 그것 은 어떻게 바 뀌 었 습 니까?그것 은 정말 계산 에 쓸 수 있 습 니까?우리 먼저 첫 번 째 문 제 를 해석 합 시다.
:
1 + ( 2 - 3 * 4 ) / 5 + 6
:
，
, . :
( ( 1 + ( ( 2 - ( 3 * 4 ) ) / 5 ) ) + 6 )
:
( ( 1 ( ( 2 ( 3 4 ) * ) - 5 ) / ) + 6 ) +
:
1 2 3 4 * - 5 / + 6 +지금 을 보 니 안개 가 낀 것 이 아 닐 까? 그 러 니 계속 내 려 다 봐 야 한다!다음 단 계 를 진행 하 다.
지금 은 바 뀐 역 폴란드 표현 식 을 어떻게 계산 하 는 지 말 해 야 한다. 그렇지 않 으 면 독자 나리 들 이 귀 찮 게 다 가 버 릴 것 이다.
역 폴란드 식 의 왼쪽 부터 첫 번 째 기 호 를 찾 아 기호 앞의 두 숫자 를 추출 하여 계산 합 니 다.
1. `*`, `3 * 4 = 12`, `1 2 12 - 5 / + 6 +`
2. `-`, `2 - 12 = -10`, `1 -10 5 / + 6 +`
3. `/`, `-10 / 5 = -2`, `1 -2 + 6 +`
4. `+`, `1 + -2 = -1`, `-1 6 +`
5. `+`, `-1 + 6 = 5`, `5`예 시 를 보고 갑자기 밝 아 졌 나 요? 표현 식 을 역 폴란드 표현 식 으로 바 꾸 면 왼쪽 에서 오른쪽으로 기호 하 나 를 검색 하면 바로 계산 할 수 있 습 니 다.괄호 의 강제 우선 연산 과 연산 자 간 의 우선 순위 관 계 를 완전히 제거 하 였 다.
3: 우 리 는 문 제 를 푸 는 사람 이 필요 하 다.
leetcode 150 제목 은 역 폴란드 표현 식 의 값 을 구 하 는 것 이다.150.
， 。
+, -, *, / 。
， 。
：
- 。
- 。
， 0 。
1：
: ["2", "1", "+", "3", "*"]
: 9
: ：((2 + 1) * 3) = 9역 폴란드 식 연산 을 실현 하려 면 스 택 을 도입 해 야 합 니 다.수치 요 소 를 순서대로 스 택 에 넣 고 기 호 를 만나면 스 택 의 마지막 두 수 치 를 스 택 에서 나 옵 니 다. 선후 순 서 를 주의 하 십시오. 먼저 스 택 을 나 온 사람 은 계산 할 때 기호 에 있 고 나중에 스 택 을 나 온 수 치 는 계산 할 때 기호 앞 에 있 습 니 다.계산 이 끝 난 후 얻 은 수 치 를 창고 에 넣 습 니 다.마지막 으로 수치 스 택 에 하나의 수치 요소 만 남아 있 습 니 다. 이것 이 바로 계산 결과 입 니 다.
class Solution:
def evalRPN(self, tokens: list[str]) -> int:
= []
for token in tokens:
if token not in "+-*/": #
.append(int(token))
else:
= .pop()
= .pop()
if token == '+':
.append( + )
elif token == '-':
.append( - )
elif token == '*':
.append( * )
elif token == '/':
.append(int( / ))
return .pop()자: 지난 문 제 는 고찰 이 전면적 이지 않 은 것 같 습 니 다.
지난 문 제 는 역 폴란드 표현 식 을 직접 보 여 주 었 으 니 우 리 는 풀 기만 하면 된다.그러면 일반적인 표현 식 만 제시 하고 역 폴란드 표현 식 으로 계산 해 야 합 니 다.그럼 코드 를 사용 해서 어떻게 해요?
def (s):
''' s ( ) '''
, , = [], [], ''
# ( )
= {
"+": {"+": '>', '-': '>', '*': ''},
"-": {"+": '>', '-': '>', '*': ''},
"*": {"+": '>', '-': '>', '*': '>', '/': '>', '(': ''},
"/": {"+": '>', '-': '>', '*': '>', '/': '>', '(': ''},
"(": {"+": '': # ,
.append( .pop())
= value
for in : # ,
.append( .pop())
return
if __name__ == "__main__":
print( ('1+(2-3*4)/5+6'))상기 코드 를 실행 한 결과 얻 은 결 과 는:
[1, 2, 3, 4, '*', '-', 5, '/', '+', 6, '+']leetcode 150 문제 와 같은 표현 식 으로 바 뀌 었 죠?그럼 다음 단 계 는 긴 말 안 해도 되 는 거 죠?오: 자신 을 홍보 하 세 요.
공중 번호: "python 잡화점" 은 python 언어 와 관련 지식 에 전념 합 니 다.더 많은 오리지널 글 을 발굴 하여 당신 의 관심 을 기대 합 니 다.
좋은 웹페이지 즐겨찾기
