百度前端技术学院是一个为大学生创办的免费的前端技术实践、分享、交流平台。由百度校园招聘组、百度校园品牌部、百度前端技术部以及多个百度的前端团队联合创办。学院组织了一批百度在职工程师,精心编写了数十个实践编码任务,将技术知识点系统有机地串联在各个充满趣味与挑战的任务中,同学们通过实际地编码练习来掌握知识,再辅以互相评价、学习笔记等方式,加深对于学习内容的理解。在过去的三年中,百度前端技术学院累积吸引了上万名同学参加,并且有数十名同学在学习后,顺利加入了百度,成为了百度的前端工程师。

中缀表达式转化为后缀表达式

作者张大珍课程算式计算器2187次浏览02017-03-10 13:15

中缀表达式

通常来说,中缀表达式即符合我们平时书写习惯的表达式。
如 计算式 
    var str = '1 + 2 * (3 - 4)'
它的特征即,操作符在操作数中间
如果将计算式转化为二叉树,那么中缀表达式即为中序遍历的结果

后缀表达式

后缀表达式,更符合计算机运算的内部存储结构——栈。
将上面式子写成后缀表达式
    var str = '1 2 3 4 - * +'
它的特征即,操作符在操作数后面
同时,去掉了可以改变运算优先级的括号,这样计算机在运算时就不用再考虑优先级的问题了
后缀表达式是二叉树后序遍历的结果

转化过程

  • 借助二叉树图形化理解过程
    其实中缀表达式转后缀表达式就是同一棵二叉树由中序遍历结果转化为后序遍历结果
    单单只有中序遍历结果是不能得到唯一的后序遍历结果的
    所以在处理时,要对操作符的优先级进行设置,得到唯一的遍历结果

  • 具体转化步骤
    在转化之前需明确:
    输入: 中缀表示式 > inputStr
    输出: 后缀表达式 > outputStr
    工具: 计算机调用栈 > stack
    步骤:

      1. 对输入串进行遍历,每次得到input[i],对每个input[i]进行判断
      2. 若input[i]为数字,添加到outputStr
      3. 若input[i]为左括号,添加到stack
      4. 若input[i]为右括号,将stack中左括号之前的操作符添加到outputStr,左括号出栈
      5. 若input[i]为操作符,
         当出现下面三种情况之一时,直接添加到stack
         - stack 为空
         - stack 栈顶 为 左括号
         - 当前input[i]的优先级高于栈顶操作符优先级
         其他情况,先将栈顶元素出栈后,再将input[i]添加到stack
      6. 遍历结束
      7. 若stack中仍有操作符,出栈,添加到outputStr
    

js代码

js中,处理数组比处理字符串更方便些,本例中将输入输出都处理成了数组。栈也由数组进行模拟。
function toRPN (str) {
    var inputStr = str.replace(/./g,'_')
                  .replace(/(/g,'(')
                  .replace(/)/g,')')
                  .replace(/(W)/g, ' $& ')
                  .replace(/_/g,'.')
                  .split(' ')
                  .filter(it => it != '')
    var outputStr = []
    var stack = []
    // 操作符 数组
    var opArr = ['+','-','*','/']
    inputStr.forEach(function(value) {
        if(Number.isNaN(Number(value)) == false) {
            outputStr.push(value)
        }
        else if(value == '(') {
            stack.push(value)
        }
        else if(value == ')') {
            while(stack[stack.length - 1] != '('){
                outputStr.push(stack.pop())
            }
            if(stack[stack.length - 1] == '('){
                stack.pop()
            }
        }
        else {
            while(stack.length > 0 
                && 
                stack[stack.length - 1] != '(' 
                && 
                property(value) <= property(stack[stack.length - 1])){
                outputStr.push(stack.pop())
            }
            stack.push(value)
        }
    })
    while(stack.length > 0) {
        outputStr.push(stack.pop())
    }

    return outputStr
    // 判断是否操作数
    function isOperator(v) {
        if(opArr.indexOf(v) > -1){
            return true
        }
        else {
            return false
        }
    }
    // 判断操作符优先级
    function property(v) {
        switch(v){
            case '+':
            case '-': return 1
            case '*':
            case '/': return 2
            default: return 0       
        }
    }
}
1条评论