首页 > 试题广场 >

表达式求值

[编程题]表达式求值
  • 热度指数：100158 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请写一个整数计算器，支持加减乘三种运算和括号。

数据范围：，保证计算结果始终在整型范围内

要求：空间复杂度： ，时间复杂度
示例1

输入

"1+2"

输出

3
示例2

输入

"(2*(3-4))*5"

输出

-10
示例3

输入

"3+2*3*4-1"

输出

26
算法知识视频讲解
添加回答
JavaScript Node
牛客823762021号头像 牛客823762021号
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */
/**
 * 获得符号优先级
 */
function getPer(item) {
    if (item === "/" || item === "*") return 2;
    if (item === "+" || item === "-") return 1;
    return 0;
}
/**
 * 通过后缀表达式计算结果
 */
function evalRPN(tokens) {
    // write code here
    const stack = [];
    function getRes(char, a, b) {
        if (char === "+") {
            return a + b;
        }
        if (char === "-") {
            return a - b;
        }
        if (char === "*") {
            return a * b;
        }
        if (char === "/") {
            return parseInt(a / b);
        }
    }
    for (let i = 0; i < tokens.length; i++) {
        if (isNaN(tokens[i])) {
            const a = stack.pop();
            const b = stack.pop();
            stack.push(getRes(tokens[i], b, a));
        } else {
            stack.push(parseInt(tokens[i]));
        }
    }
    return stack[0];
}
/**
 * 获得后缀表达式
 */
function getRule(list) {
    const stack = []; // 转后缀表达式
    const operation = []; // 运算符栈
    list.forEach((item) => {
        // 数字直接进栈
        if (!isNaN(item)) {
            stack.push(item);
        } else {
            if (item === "(") {
                // 左括号直接入操作栈
                operation.push(item);
            } else if (item === ")") {
                // 如果是右括号,要一直把操作栈里面的操作符弹出，直到遇到“（”

                while (
                    operation.length &&
                    operation[operation.length - 1] !== "("
                ) {
                    stack.push(operation.pop());
                }
                if (
                    operation.length &&
                    operation[operation.length - 1] === "("
                ) {
                    operation.pop();
                }
                return;
            } else {
                // 其他操作符，运算栈栈顶的优先级 >= 当前操作符优先级，弹出运算栈栈顶元素
                while (
                    operation.length &&
                    getPer(operation[operation.length - 1]) >= getPer(item)
                ) {
                    stack.push(operation.pop());
                }
                operation.push(item);
            }
        }
    });
    while (operation.length) {
        stack.push(operation.pop());
    }
    return stack;
}
function solve(s) {
    // write code here
    // 获取操作栈，主要处理可能多位数字
    const list = [];
    let i = 0;
    while (i < s.length) {
        if (isNaN(s[i])) {
            list.push(s[i]);
            i++;
            continue;
        }
        // 最后一位数字
        if (i === s.length - 1) {
            list.push(s[i]);
            break;
        } else {
            // 否则一直截取到下一个操作符前一位
            let j = i;
            while (!isNaN(s[j + 1])) {
                j++;
            }
            list.push(s.slice(i, j + 1));
            i = j + 1;
        }
    }
    const stack = getRule(list);

    return evalRPN(stack);
}
发表于 2025-07-09 22:44:16 回复(0)
JavaScript Node
牛客710667568号头像 牛客710667568号
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */
function solve(s) {
    let data = new Array();
    let temp = "";
    for (let i = 0; i < s.length; i++) {
        if (/[0-9]/.test(s[i])) {
            temp += s[i];
            if(i == s.length-1 && /[0-9]/.test(s[i])) {
                data.push(temp);
            }
            // console.log(temp)
        } else if (/[^0-9]/.test(s[i]) && temp !== "") {
            data.push(temp);
            data.push(s[i]);
            temp = '';
        } else {
            data.push(s[i]);
            // console.log(s[i]);
        }

    }
    console.log(data);
    // console.log(s[0])
    let stack = [];
    let chStack = [];
    for (let i = 0; i < data.length; i++) {
        if (/[0-9]/.test(data[i])) {
            stack.push(data[i]);
        } else if (data[i] == ")") {
            let temp = 0;
            while (chStack[chStack.length - 1] !== "(") {
                switch (chStack[chStack.length - 1]) {
                    case "+":
                        temp =
                            parseInt(stack[stack.length - 2]) +
                            parseInt(stack[stack.length - 1]);
                        stack.pop();
                        stack.pop();
                        chStack.pop();
                        break;
                    case "-":
                        temp =
                            parseInt(stack[stack.length - 2]) -
                            parseInt(stack[stack.length - 1]);
                        stack.pop();
                        stack.pop();
                        chStack.pop();
                        break;
                    case "*":
                        temp =
                            parseInt(stack[stack.length - 2]) *
                            parseInt(stack[stack.length - 1]);
                        stack.pop();
                        stack.pop();
                        chStack.pop();
                        break;
                    case "/":
                        temp =
                            parseInt(stack[stack.length - 2]) /
                            parseInt(stack[stack.length - 1]);
                        stack.pop();
                        stack.pop();
                        chStack.pop();
                        break;
                }
                stack.push(temp);
            }
            chStack.pop();
        } else {
            if (
                (data[i] == "+" || data[i] == "-") &&
                (chStack[chStack.length - 1] == "*" ||
                    chStack[chStack.length - 1] == "/")
            ) {
                let temp = 0;
                switch (chStack[chStack.length - 1]) {
                    case "*":
                        temp =
                            parseInt(stack[stack.length - 2]) *
                            parseInt(stack[stack.length - 1]);
                        break;
                    case "/":
                        temp =
                            parseInt(stack[stack.length - 2]) /
                            parseInt(stack[stack.length - 1]);
                        break;
                }
                stack.pop();
                stack.pop();
                stack.push(temp);
                chStack.pop();
                chStack.push(data[i]);
            } else {
                chStack.push(data[i]);
            }
        }
    }
    if (stack.length == 1) {
        console.log("jjj")
        return stack[0];
    } else {
        let temp = parseInt(stack[0]);
        stack.shift();
        while (chStack.length) {
           
            switch (chStack[0]) {
                case "+":
                    temp = temp + parseInt(stack[0])
                    stack.shift();
                    chStack.shift();
                    break;
                case "-":
                    temp = temp - parseInt(stack[0])
                    stack.shift();
                    chStack.shift();
                    break;
                case "*":
                    temp = temp * parseInt(stack[0])
                    stack.shift();
                    chStack.shift();
                    break;
                case "/":
                    temp = temp / parseInt(stack[0])
                    stack.shift();
                    chStack.shift();
                    break;
            }
        }
        return temp;
    }
    // write code here
}
module.exports = {
    solve: solve,
};

发表于 2023-09-07 12:13:31 回复(0)
JavaScript Node
果冻~头像 果冻~ 
// 第一种方法
function solve( s ){
    let stack = [],i = 0,sign='+',num=0; 
    while(i < s.length){
        if(s[i]=='('){
            let flag= 1, start = i+1;
            while(flag>0){
                i++;
                if(s[i]==')') flag--;
                if(s[i]=='(') flag++;
            }
            num = solve(s.slice(start,i));
            i--;
        }else if(s[i]>='0'&&s[i]<='9'){
            num = num*10 + Number(s[i]);
        }
        if((s[i]<'0'|| s[i]>'9') || i==s.length-1){
            if(sign=='*') stack.push(Number(stack.pop())*num);
            if(sign=='+') stack.push(Number(num));
            if(sign=='-') stack.push(Number(num)*-1);
            if(sign=='/') stack.push(Number(stack.pop())/num);
            sign = s[i];
            num = 0;
        }
        i++;
    }
    return stack.reduce((total,n)=>{return total+n},0);
}
// 第二种
function solve ( s ) {
    return eval(s);
}
// 第三种
function solve ( s ) {
    let func = new Function(`return ${s}`);
    return func();
}

发表于 2021-09-05 14:22:11 回复(6)
提交观点

问题信息

栈 递归
难度：
3条回答 9454浏览

热门推荐

通过挑战的用户

查看代码

相关试题

表达式求值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号