阅读 194

逆波兰表达式

什么是逆波兰表达式?

运算符在操作数的后面 3 * 4 ===> 3 4 *, 所以也被称为后缀表达式。

使用逆波兰表达式时,是不需要使用括号的。在中缀表达式中,例如:(3 - 4) * 5,我们需要使用括号提高减号的优先级,而在逆波兰表达式中是不需要使用括号的,3 4 - 5 * ,直接在3 4操作数后面跟着一个-号, 就可以表示3 - 4是首先计算的。

再举几个例子:

  • 3 - 4 * 5 ===> 3 4 5 * -
  • (4 + (13 / 5)) ===> 4 13 5 / +
  • ((2 + 1) * 3) = 9 ===> 2 1 + 3 *

手动计算逆波兰表达式

面对一个复杂逆波兰表达式,我们改如何计算呢?

例如:10 6 9 3 + -11 * / * 17 + 5 +

我们首先从头开始遍历逆波兰表达式字符串

  1. 遇到第一个 +9 + 3 = 12,现在的表达式是,10 6 12 -11 * / * 17 + 5 +
  2. 遇到第二个 *12 * -11 = -132,现在的表达式是 10 6 -132 / * 17 + 5 +
  3. 遇到第三个 /6 / -132 = -0.04,现在的表达式 10 -0.04 * 17 + 5 +
  4. 遇到第四个 *10 * -0.04 = -0.4,现在的表达式 -0.4 17 + 5 +
  5. 遇到第五个 +-0.4 + 17 = 16.6,现在的表达式 16.6 5 +
  6. 遇到第六个 +16.6 + 5 = 21.6

中缀表达式的转换

如何将中缀表达式转换为逆波兰表达式?我们需要借助两个堆栈,一个堆栈存放数字,一个堆栈存放运算符。

举一个例子:(2 + 1) * 3

// 第一步,遇到 ( 不处理
=======        =======
|   |         |   |
|   |         |   |
|   |         |   |
|   |         |   |
|   |         |   |
=======        =======
 数字            操作符

// 第二步,遇到 2 ,添加到数字堆栈中
=======        =======
|   |         |   |
|   |         |   |
|   |         |   |
|   |         |   |
| 2 |         |   |
=======        =======
 数字            操作符

// 第三步遇到 +, 添加到操作符堆栈
=======        =======
|   |         |   |
|   |         |   |
|   |         |   |
|   |         |   |
| 2 |         | + |
=======        =======
 数字            操作符

// 第四步遇到 1, 添加到数字堆栈
=======        =======
|   |         |   |
|   |         |   |
|   |         |   |
| 1 |         |   |
| 2 |         | + |
=======        =======
 数字            操作符

// 第五步遇到 ), 将操作符堆栈的顶部弹出,push到数字堆栈中
=======        =======
|   |         |   |
|   |         |   |
| + |         |   |
| 1 |         |   |
| 2 |         |   |
=======        =======
 数字            操作符

// 第六步
=======        =======
|   |         |   |
|   |         |   |
| + |         |   |
| 1 |         |   |
| 2 |         | * |
=======        =======
 数字            操作符

// 第七步
=======        =======
|   |         |   |
| 3 |         |   |
| + |         |   |
| 1 |         |   |
| 2 |         | * |
=======        =======
 数字            操作符

// 第八步,将操作符依次弹出,添加到数字堆栈中
=======        =======
|   |         |   |
| 3 |         |   |
| + |         |   |
| 1 |         |   |
| 2 |         | * |
=======        =======
 数字            操作符

=======        =======
| * |         |   |
| 3 |         |   |
| + |         |   |
| 1 |         |   |
| 2 |         |   |
=======        =======
 数字            操作符

结果如下: 2 1 + 3 *
复制代码

代码实现 ↓↓↓↓↓↓↓

// 一个js版本的堆栈
class Stack {
    constructor () {
        this.stack = []
    }
    push (v) {
        this.stack.push(v)
    }
    pop () {
        return this.stack.pop()
    }
    top () {
        return this.stack[this.stack.length - 1]
    }
    size () {
        return this.stack.length
    }
}
复制代码
// 中缀表达式
const expression = '( ( 10 * ( 6 / ( ( 9 + 3 ) * -11 ) ) ) + 17 ) + 5'

const transformRPN = (expression) => {
    const operator = ['+', '-', '*', '/']

    // 运算符的堆栈
    const operatorStack = new Stack()

    // 数字的堆栈
    const operandStack = new Stack()

    const tokens = expression.split(' ')

    for (let i = 0; i < tokens.length; i++) {
        const token = tokens[i]
        if (operator.includes(token)) {
            operatorStack.push(token)
        } else {
            if (token === ')') {
                operandStack.push(operatorStack.pop())
            } else {
                if (
                    typeof Number(token) === 'number' &&
                    !isNaN(Number(token))
                ) {
                    operandStack.push(token)
                }
            }
        }
    }

    while (operatorStack.size()) {
        operandStack.push(operatorStack.pop())
    }
}

transformRPN(expression)

复制代码

代码实现逆波兰表达式的计算

leetcode,150题也是类似的题目。

举一个例子:2 1 + 3 *


// 第一步
=======        
|   |         
|   |         
|   |      
|   |       
| 2 |      
=======   

// 第二步
=======        
|   |         
|   |         
|   |      
| 1 |       
| 2 |      
======= 

// 第三步,遇到运算符,从堆栈中弹出两个进行计算 2 + 1 = 3
=======        
|   |         
|   |         
|   |      
|   |       
| 3 |      
======= 

// 第四步
=======        
|   |         
|   |         
|   |      
| 3 |       
| 3 |      
======= 

// 第五步,遇到运算符,从堆栈中弹出两个进行计算 3 * 3 = 9
=======        
|   |         
|   |         
|   |      
|   |       
| 9 |      
======= 

// 得到结果 9
复制代码

代码实现 ↓↓↓↓↓↓↓


const evalRPN = (tokens) => {
    const operator = ['+', '-', '*', '/']

    const stack = new Stack()

    for (let i = 0; i < tokens.length; i++) {
        if (operator.includes(tokens[i])) {
            const a = Number(stack.pop())
            const b = Number(stack.pop())
            let result = null
            switch (tokens[i]) {
                case '+':
                    result = a + b 
                    break
                case '-':
                    result = b - a
                    break
                case '*':
                    result = a * b
                    break
                case '/':
                    result = b / a
                    break
            }
            stack.push(result)
        } else {
            stack.push(tokens[i])
        }
    }

    return stack.top()
};
复制代码

参考