什么是逆波兰式?
逆波兰式的英文全称是“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中文网!!

핫 AI 도구

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

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

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

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

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

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

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

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

뜨거운 주제











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

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

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

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

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

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

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

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