백엔드 개발 PHP 튜토리얼 什么是逆波兰式?

什么是逆波兰式?

Jun 13, 2016 am 11:01 AM

逆波兰式的英文全称是“Reverse Polish notation”,也叫后缀表达式,逆波兰式在计算机看来是比较简单易懂的结构,因为计算机普遍采用的内存结构是栈式结构,它执行先进后出的顺序。

什么是逆波兰式?

什么是逆波兰式?

逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后),指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。

后缀表达式计算:

后缀表达式计算与前缀表达式类似,只是顺序是从左至右,具体过程如下:

从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果

例如:后缀表达式为“2 3 + 4 × 5 -”计算过程如下:

  (1)从左至右扫描,将 2 和 3 压入堆栈;

  (2)遇到 + 运算符,因此弹出 3 和 2( 3 为栈顶元素,2 为次顶元素,注意与前缀表达式做比较),计算出 3+2 的值,得 5,再将 5 入栈;

  (3)将 4 入栈;

  (4)接下来是 × 运算符,因此弹出 4 和 5,计算出 4 × 5 = 20,将 20 入栈;

  (5)将 5 入栈;

  (6)最后是-运算符,计算出 20-5 的值,即 15,由此得出最终结果。

中缀表达式转后缀表达式:

与转换为前缀表达式相似,步骤如下:

  (1)初始化两个栈:运算符栈s1和储存中间结果的栈s2;

  (2)从左至右扫描中缀表达式;

  (3)遇到操作数时,将其压s2;

  (4)遇到运算符时,比较其与 s1 栈顶运算符的优先级:

    a:如果 s1 为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;

    b:否则,若优先级比栈顶运算符的高,也将运算符压入 s1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);

    c:否则,将 s1 栈顶的运算符弹出并压入到 s2 中,再次转到(4)-(1)与s1中新的栈顶运算符相比较;

  (5)遇到括号时:

    a:如果是左括号“(”,则直接压入 s1;

    b:如果是右括号“)”,则依次弹出 s1 栈顶的运算符,并压入 s2 ,直到遇到左括号为止,此时将这一对括号丢弃;

  (6)重复步骤(2)至(5),直到表达式的最右边;

  (7)将 s1 中剩余的运算符依次弹出并压入 s2;

  (8)依次弹出 s2 中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)

例如,将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下:

(a+b)*c-(a+b)/e

→((a+b)*c)((a+b)/e)-

→((a+b)c*)((a+b)e/)-

→(ab+c*)(ab+e/)-

→ab+c*ab+e/-

扫描到的元素 s2(栈底->栈顶) s1 (栈底->栈顶) 说明
1 1 数字,直接入栈
+ 1 + s1为空,运算符直接入栈
( 1 + ( 左括号,直接入栈
( 1 + ( ( 同上
2 1 2 + ( ( 数字
+ 1 2 + ( ( + s1栈顶为左括号,运算符直接入栈
3 1 2 3 + ( ( + 数字
) 1 2 3 + + ( 右括号,弹出运算符直至遇到左括号
× 1 2 3 + + ( × s1栈顶为左括号,运算符直接入栈
4 1 2 3 + 4 + ( × 数字
) 1 2 3 + 4 × + 右括号,弹出运算符直至遇到左括号
- 1 2 3 + 4 × + - -与+优先级相同,因此弹出+,再压入-
5 1 2 3 + 4 × + 5 - 数字
到达最右端 1 2 3 + 4 × + 5 - s1中剩余的运算符

得到的最终结果为:“ 1 2 3 + 4 × + 5 - ”

逆波兰式的作用

实现逆波兰式的算法,难度并不大,但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式?原因就在于这个简单是相对人类的思维结构来说的,对计算机而言中序表达式是非常复杂的结构。相对的,逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构,它执行先进后出的顺序。

更多相关知识,请访问 PHP中文网!!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

11 최고의 PHP URL 쇼트너 스크립트 (무료 및 프리미엄) 11 최고의 PHP URL 쇼트너 스크립트 (무료 및 프리미엄) Mar 03, 2025 am 10:49 AM

종종 키워드와 추적 매개 변수로 혼란스러워하는 긴 URL은 방문자를 방해 할 수 있습니다. URL 단축 스크립트는 솔루션을 제공하여 소셜 미디어 및 기타 플랫폼에 이상적인 간결한 링크를 만듭니다. 이 스크립트는 개별 웹 사이트 a에 유용합니다

Instagram API 소개 Instagram API 소개 Mar 02, 2025 am 09:32 AM

Instagram은 2012 년 Facebook에서 유명한 인수에 이어 타사 사용을 위해 두 개의 API 세트를 채택했습니다. Instagram Graph API 및 Instagram Basic Display API입니다. 개발자는

Laravel의 플래시 세션 데이터로 작업합니다 Laravel의 플래시 세션 데이터로 작업합니다 Mar 12, 2025 pm 05:08 PM

Laravel은 직관적 인 플래시 방법을 사용하여 임시 세션 데이터 처리를 단순화합니다. 응용 프로그램에 간단한 메시지, 경고 또는 알림을 표시하는 데 적합합니다. 데이터는 기본적으로 후속 요청에만 지속됩니다. $ 요청-

Laravel Back End : Part 2, React가있는 React 앱 구축 Laravel Back End : Part 2, React가있는 React 앱 구축 Mar 04, 2025 am 09:33 AM

이것은 Laravel 백엔드가있는 React Application을 구축하는 데있어 시리즈의 두 번째이자 마지막 부분입니다. 이 시리즈의 첫 번째 부분에서는 기본 제품 목록 응용 프로그램을 위해 Laravel을 사용하여 편안한 API를 만들었습니다. 이 튜토리얼에서는 Dev가 될 것입니다

Laravel 테스트에서 단순화 된 HTTP 응답 조롱 Laravel 테스트에서 단순화 된 HTTP 응답 조롱 Mar 12, 2025 pm 05:09 PM

Laravel은 간결한 HTTP 응답 시뮬레이션 구문을 제공하여 HTTP 상호 작용 테스트를 단순화합니다. 이 접근법은 테스트 시뮬레이션을보다 직관적으로 만들면서 코드 중복성을 크게 줄입니다. 기본 구현은 다양한 응답 유형 단축키를 제공합니다. Illuminate \ support \ Facades \ http를 사용하십시오. http :: 가짜 ([ 'google.com'=> ​​'Hello World', 'github.com'=> ​​[ 'foo'=> 'bar'], 'forge.laravel.com'=>

PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법 PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법 Mar 14, 2025 am 11:42 AM

PHP 클라이언트 URL (CURL) 확장자는 개발자를위한 강력한 도구이며 원격 서버 및 REST API와의 원활한 상호 작용을 가능하게합니다. PHP CURL은 존경받는 다중 프로모토콜 파일 전송 라이브러리 인 Libcurl을 활용하여 효율적인 execu를 용이하게합니다.

Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트 Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트 Mar 13, 2025 pm 12:08 PM

고객의 가장 긴급한 문제에 실시간 인스턴트 솔루션을 제공하고 싶습니까? 라이브 채팅을 통해 고객과 실시간 대화를 나누고 문제를 즉시 해결할 수 있습니다. 그것은 당신이 당신의 관습에 더 빠른 서비스를 제공 할 수 있도록합니다.

2025 PHP 상황 조사 발표 2025 PHP 상황 조사 발표 Mar 03, 2025 pm 04:20 PM

2025 PHP Landscape Survey는 현재 PHP 개발 동향을 조사합니다. 개발자와 비즈니스에 대한 통찰력을 제공하는 프레임 워크 사용, 배포 방법 및 과제를 탐색합니다. 이 조사는 현대 PHP Versio의 성장을 예상합니다

See all articles