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

Reasons for PHPSession failure include configuration errors, cookie issues, and session expiration. 1. Configuration error: Check and set the correct session.save_path. 2.Cookie problem: Make sure the cookie is set correctly. 3.Session expires: Adjust session.gc_maxlifetime value to extend session time.

Methods to debug session problems in PHP include: 1. Check whether the session is started correctly; 2. Verify the delivery of the session ID; 3. Check the storage and reading of session data; 4. Check the server configuration. By outputting session ID and data, viewing session file content, etc., you can effectively diagnose and solve session-related problems.

Multiple calls to session_start() will result in warning messages and possible data overwrites. 1) PHP will issue a warning, prompting that the session has been started. 2) It may cause unexpected overwriting of session data. 3) Use session_status() to check the session status to avoid repeated calls.

Configuring the session lifecycle in PHP can be achieved by setting session.gc_maxlifetime and session.cookie_lifetime. 1) session.gc_maxlifetime controls the survival time of server-side session data, 2) session.cookie_lifetime controls the life cycle of client cookies. When set to 0, the cookie expires when the browser is closed.

The main advantages of using database storage sessions include persistence, scalability, and security. 1. Persistence: Even if the server restarts, the session data can remain unchanged. 2. Scalability: Applicable to distributed systems, ensuring that session data is synchronized between multiple servers. 3. Security: The database provides encrypted storage to protect sensitive information.

Implementing custom session processing in PHP can be done by implementing the SessionHandlerInterface interface. The specific steps include: 1) Creating a class that implements SessionHandlerInterface, such as CustomSessionHandler; 2) Rewriting methods in the interface (such as open, close, read, write, destroy, gc) to define the life cycle and storage method of session data; 3) Register a custom session processor in a PHP script and start the session. This allows data to be stored in media such as MySQL and Redis to improve performance, security and scalability.

SessionID is a mechanism used in web applications to track user session status. 1. It is a randomly generated string used to maintain user's identity information during multiple interactions between the user and the server. 2. The server generates and sends it to the client through cookies or URL parameters to help identify and associate these requests in multiple requests of the user. 3. Generation usually uses random algorithms to ensure uniqueness and unpredictability. 4. In actual development, in-memory databases such as Redis can be used to store session data to improve performance and security.

Managing sessions in stateless environments such as APIs can be achieved by using JWT or cookies. 1. JWT is suitable for statelessness and scalability, but it is large in size when it comes to big data. 2.Cookies are more traditional and easy to implement, but they need to be configured with caution to ensure security.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

VSCode Windows 64-bit Download
A free and powerful IDE editor launched by Microsoft

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment
