波蘭表達式的全面解析

一、波蘭表達式c

波蘭表達式也叫前綴表達式，是一種不需要括弧即可表示複雜運算的表達式。以波蘭數學家Jan Łukasiewicz的名字命名。和我們平時所寫的算術表達式中綴表達式有所不同，波蘭表達式的運算符位於操作數之前。

波蘭表達式的一般形式為：「運算符 操作數1 操作數2」 ，例如中綴表達式(1+2）*3對應的波蘭表達式為*+123。

二、波蘭表達式解析邏輯運算符

對於中綴表達式中的邏輯運算符（&&,||,!），我們可以通過波蘭表達式來替換掉這些運算符，即用對應的波蘭表達式來表示邏輯運算符的運算關係。其中，&&對應and，||對應or，!對應not，具體可以參考下表。

邏輯運算符 	中綴表達式 	波蘭表達式
&&       a && b       & a b
||       a || b       | a b
!        !a           ! a 

三、波蘭表達式代碼

下面是一個簡單的波蘭表達式計算的Python代碼示例：

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token in ["+", "-", "*", "/"]:
                a = stack.pop()
                b = stack.pop()
                if token == "+":
                    stack.append(b + a)
                elif token == "-":
                    stack.append(b - a)
                elif token == "*":
                    stack.append(b * a)
                else:
                    stack.append(int(b / a))
            else:
                stack.append(int(token))
        return stack[0]

四、波蘭表達式與二叉樹

波蘭表達式可以通過二叉樹來表示，二叉樹的結點表示運算符或操作數，左結點和右結點分別表示運算符或操作數的左側和右側。二叉樹的葉結點都是操作數。比如表達式（8-3）*（2+6）的二叉樹表示如下：

            *
          /   \
        -      +
      /  \    / \
     8    3  2   6

五、波蘭表達式怎麼算

計算波蘭表達式通常使用棧來實現，從左到右遍歷表達式，如果是一個操作數，則入棧，如果是一個運算符，則取出棧頂的兩個元素進行運算，並把運算結果入棧。當表達式遍歷完成後，棧中的唯一元素就是表達式的計算結果。比如計算波蘭表達式（2,1,+,3,*）的結果可以按照以下步驟來實現：

1. 將2和1壓入棧中；
2. 彈出2和1（1在棧頂），計算2+1，結果為3，將3壓入棧中；
3. 將3和3壓入棧中；
4. 彈出3和3（3在棧頂），計算3*3，結果為9，將9壓入棧中；
5. 棧中的唯一元素9就是表達式的計算結果。

六、波蘭表達式是什麼

波蘭表達式是將運算符前置的一種數學表達式，由波蘭數學家Jan Łukasiewicz於1920年提出並命名。波蘭表達式有著與中綴表達式類似的計算結果，但由於運算符的位置不同，波蘭表達式更適用於計算機處理。

七、波蘭表達式怎麼寫

在使用時，可以按照以下步驟將中綴表達式轉換為波蘭表達式：

1. 創建一個運算符棧和一個結果棧；
2. 從左到右遍歷中綴表達式中的每個元素；
3. 如果遇到操作數，將其壓入結果棧中；
4. 如果遇到運算符，則與運算符棧頂的元素進行比較：
   4.1 如果該運算符的優先順序高於運算符棧頂的元素，則將該運算符壓入運算符棧中；
   4.2 如果該運算符的優先順序低於或等於運算符棧頂的元素，則不斷彈出運算符棧頂的元素，直到遇到優先順序低於該運算符的元素，然後將該運算符壓入運算符棧中；
5. 如果遇到左括弧，將其壓入運算符棧中；
6. 如果遇到右括弧，則連續彈出運算符棧頂元素並壓入結果棧中，直到彈出的元素是左括弧為止；
7. 遍歷完成後，如果運算符棧中仍有元素，則依次彈出並壓入結果棧中；
8. 將結果棧中的元素逆序輸出即得到波蘭表達式。

八、波蘭表達式前中後的區別

波蘭表達式有前綴、中綴和後綴（逆波蘭）三種形式，中綴表達式是人們最為熟悉的，並且使用得也最多，但計算機計算的時候需要先轉化為其他形式再進行計算。波蘭表達式與中綴表達式之間的轉換主要包括：

中綴表達式 -> 前綴表達式：使用不斷彈出棧頂元素的方法，將中綴表達式轉換為前綴表達式；
中綴表達式 -> 後綴表達式：使用不斷彈出棧頂元素的方法，將中綴表達式轉換為逆波蘭表達式；
前綴表達式 -> 中綴表達式：使用遞歸的方法將前綴表達式轉換為中綴表達式；
後綴表達式 -> 中綴表達式：使用遞歸的方法將後綴表達式轉換為中綴表達式。

九、波蘭表達式和逆波蘭表達式定義

波蘭表達式通常指前綴表達式，也稱為波蘭記法，是一種將運算符寫在前面的算術表達式。逆波蘭表達式通常指後綴表達式，也稱為逆波蘭記法，是一種將運算符寫在後面的算術表達式。逆波蘭表達式與波蘭表達式類似，但運算符位於操作數之後。例如，中綴表達式 (1+2)*(3+4) 可以寫成逆波蘭表達式 1 2 + 3 4 + *

十、波蘭表達式例題

1、LeetCode 150. Evaluate Reverse Polish Notation

給定一個代表逆波蘭表達式的字元串，求表達式的值。可以假設給定的逆波蘭表達式始終有效，且所有中間結果的計算值在範圍 [-2^31, 2^31 – 1] 內。

示例：

輸入: ["2", "1", "+", "3", "*"]
輸出: 9

AC代碼如下：

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token in ["+", "-", "*", "/"]:
                a = stack.pop()
                b = stack.pop()
                if token == "+":
                    stack.append(b + a)
                elif token == "-":
                    stack.append(b - a)
                elif token == "*":
                    stack.append(b * a)
                else:
                    stack.append(int(b / a))
            else:
                stack.append(int(token))
        return stack[0]

2、LeetCode 224. Basic Calculator

給你一個字元串表達式 s ，請你實現一個基本計算器來計算並返回它的值。示例 1：

輸入：s = "1 + 1"
輸出：2

AC代碼如下：

class Solution:
    def calculate(self, s: str) -> int:
        num = 0 # 維護一個當前的數字
        stack = [1] # 維護一個存放+，-號的棧，遇到左括弧的時候入棧最後結果 * 對應的數字
        sign = 1 # 維護當前的符號
        res = 0 # 維護最終的結果
        for i in range(0, len(s)):
            if s[i].isdigit():
                num = num * 10 + int(s[i])
            elif s[i] == '+':
                res += sign * num
                num = 0
                sign = stack[-1]
            elif s[i] == '-':
                res += sign * num
                num = 0
                sign = -1 * stack[-1]
            elif s[i] == '(':
                stack.append(sign)
            elif s[i] == ')':
                stack.pop()
            else:
                continue
        res += sign * num
        return res

3、LeetCode 439. Ternary Expression Parser

給一個字元串表示一個三元表達式，求它的計算結果。表達式由字元串組成，其中的操作符將提供為字元。條件運算符 ? 總是以雙字元 ‘ ? ‘ 和 ‘ : ‘ 的形式出現在表達式中。

示例：

輸入： "T?2:3"
輸出： 2

AC代碼如下：

class Solution:
    def parseTernary(self, expression: str) -> str:
        if len(expression) == 1:
            return expression
        i = 0
        count = 0
        # 用來統計？和：的數量,記錄下當前的數字
        for i in range(len(expression)):
            if expression[i] == "?":
                count += 1
            elif expression[i] == ":":  
                count -= 1

            if count == 0:
                idx = i
                break
                
        return self.parseTernary(expression[2:idx+1]) if expression[0]=="T" else self.parseTernary(expression[idx+1:])