WIKI地址

逆波兰表达式

在线测试

逆波兰计算器

核心代码

const leftBracket = '('
const rightBracked = ')'

const ops = {
    ['+']: {
        level: 1,
        calc: (a, b) => a + b
    },
    ['-']: {
        level: 1,
        calc: (a, b) => a - b
    },
    ['*']: {
        level: 2,
        calc: (a, b) => a * b
    },
    ['/']: {
        level: 2,
        calc: (a, b) => a / b
    },
}

function isNumber(v) {
    return /\d+/.test(v)
}

function parseExp(express) {
    let preVal = ''
    let res = []

    for (let i = 0, len = express.length; i < len; i++) {
        if (isNumber(express[i])) {
            preVal += express[i]
        } else {
            if (preVal) res.push(preVal)
            res.push(express[i])
            preVal = ''
        }
    }
    if (preVal) res.push(preVal)

    return res
}

function parseRPN(express) {
    let res = []
    let sop = []
    let sopInd = -1
    let exps = parseExp(express)

    exps.forEach(v => {
        if (isNumber(v)) {
            res.push(v)
        } else if (v in ops) {
            while (sop.length && sop[sopInd] in ops && ops[sop[sopInd]].level >= ops[v].level) {
                res.push(sop.pop())
                sopInd--
            }
            sop.push(v)
            sopInd++
        } else {
            if (v === leftBracket) {
                sop.push(v)
                sopInd++
            } 
            if (v === rightBracked) {
                while (sop.length && sop[sopInd] !== leftBracket) {
                    res.push(sop.pop())
                    sopInd--
                }
                if (sop.length) {
                    sop.pop()
                    sopInd--
                }
            }
        }
    })

    while (sop.length) {
        res.push(sop.pop())
        sopInd--
    }

    return res
}

function calculator(express) {
    let stack = []
    let rpn = parseRPN(express)

    rpn.forEach(v => {
        if (isNumber(v)) {
            stack.push(v)
        } else if (v in ops) {
            let n1 = stack.pop()
            let n2 = stack.pop()

            stack.push(ops[v].calc(Number(n2), Number(n1)))
        }
    })

    return stack.pop()
}