公式计算器

[题目链接](https://www.nowcoder.com/practice/b2ee481ca45c4c57b6ef5dfad1c86197)

思路

题目要求读入一个包含加、减、乘、幂四种运算的公式字符串，计算并输出结果。公式中可能出现 pow(a, b) 形式的幂运算。

Python / JavaScript：直接 eval

Python 内置 pow 函数，直接 eval(input()) 即可完成全部计算。

JavaScript 中没有全局 pow，但有 Math.pow，因此将输入中的 pow( 替换为 Math.pow( 后再 eval 即可。

C++ / Java：递归下降解析器

对于不支持安全 eval 的语言，需要手写表达式解析器。按照运算符优先级，定义如下文法：

expr   -> term (('+' | '-') term)*
term   -> factor ('*' factor)*
factor -> '-' factor | atom
atom   -> NUMBER | 'pow' '(' expr ',' expr ')' | '(' expr ')'

• expr 处理加减，优先级最低。
• term 处理乘法。
• factor 处理一元负号。
• atom 处理数字字面量、pow() 函数调用和括号分组。

用一个全局指针 pos 扫描字符串，每个函数消费自己对应的语法结构并返回计算结果。

代码

[sol-Python3]

print(eval(input()))

[sol-C++]

#include <bits/stdc++.h>
using namespace std;

string s;
int pos;

void skipSpaces() {
    while (pos < (int)s.size() && s[pos] == ' ') pos++;
}

long long parseExpr();
long long parseTerm();
long long parseFactor();
long long parseAtom();

long long parseExpr() {
    long long val = parseTerm();
    while (true) {
        skipSpaces();
        if (pos < (int)s.size() && s[pos] == '+') {
            pos++; val += parseTerm();
        } else if (pos < (int)s.size() && s[pos] == '-') {
            pos++; val -= parseTerm();
        } else break;
    }
    return val;
}

long long parseTerm() {
    long long val = parseFactor();
    while (true) {
        skipSpaces();
        if (pos < (int)s.size() && s[pos] == '*') {
            pos++; val *= parseFactor();
        } else break;
    }
    return val;
}

long long parseFactor() {
    skipSpaces();
    if (pos < (int)s.size() && s[pos] == '-') {
        pos++;
        return -parseFactor();
    }
    return parseAtom();
}

long long myPow(long long base, long long exp) {
    if (exp < 0) return 0;
    long long result = 1;
    bool neg = false;
    if (base < 0 && exp % 2 == 1) { neg = true; base = -base; }
    else if (base < 0) { base = -base; }
    for (long long i = 0; i < exp; i++) result *= base;
    return neg ? -result : result;
}

long long parseAtom() {
    skipSpaces();
    if (pos + 2 < (int)s.size() && s.substr(pos, 3) == "pow") {
        pos += 3;
        skipSpaces();
        pos++; // '('
        long long a = parseExpr();
        skipSpaces();
        pos++; // ','
        long long b = parseExpr();
        skipSpaces();
        pos++; // ')'
        return myPow(a, b);
    }
    if (pos < (int)s.size() && s[pos] == '(') {
        pos++;
        long long val = parseExpr();
        skipSpaces();
        pos++; // ')'
        return val;
    }
    long long val = 0;
    bool neg = false;
    if (pos < (int)s.size() && s[pos] == '-') { neg = true; pos++; }
    while (pos < (int)s.size() && isdigit(s[pos])) {
        val = val * 10 + (s[pos] - '0');
        pos++;
    }
    return neg ? -val : val;
}

int main() {
    getline(cin, s);
    pos = 0;
    cout << parseExpr() << endl;
    return 0;
}

[sol-Java]

import java.util.Scanner;

public class Main {
    static String s;
    static int pos;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        s = sc.nextLine();
        pos = 0;
        System.out.println(parseExpr());
    }

    static void skipSpaces() {
        while (pos < s.length() && s.charAt(pos) == ' ') pos++;
    }

    static long parseExpr() {
        long val = parseTerm();
        while (true) {
            skipSpaces();
            if (pos < s.length() && s.charAt(pos) == '+') {
                pos++; val += parseTerm();
            } else if (pos < s.length() && s.charAt(pos) == '-') {
                pos++; val -= parseTerm();
            } else break;
        }
        return val;
    }

    static long parseTerm() {
        long val = parseFactor();
        while (true) {
            skipSpaces();
            if (pos < s.length() && s.charAt(pos) == '*') {
                pos++; val *= parseFactor();
            } else break;
        }
        return val;
    }

    static long parseFactor() {
        skipSpaces();
        if (pos < s.length() && s.charAt(pos) == '-') {
            pos++;
            return -parseFactor();
        }
        return parseAtom();
    }

    static long myPow(long base, long exp) {
        if (exp < 0) return 0;
        long result = 1;
        boolean neg = false;
        if (base < 0 && exp % 2 == 1) { neg = true; base = -base; }
        else if (base < 0) { base = -base; }
        for (long i = 0; i < exp; i++) result *= base;
        return neg ? -result : result;
    }

    static long parseAtom() {
        skipSpaces();
        if (pos + 2 < s.length() && s.substring(pos, pos + 3).equals("pow")) {
            pos += 3;
            skipSpaces();
            pos++; // '('
            long a = parseExpr();
            skipSpaces();
            pos++; // ','
            long b = parseExpr();
            skipSpaces();
            pos++; // ')'
            return myPow(a, b);
        }
        if (pos < s.length() && s.charAt(pos) == '(') {
            pos++;
            long val = parseExpr();
            skipSpaces();
            pos++; // ')'
            return val;
        }
        long val = 0;
        boolean neg = false;
        if (pos < s.length() && s.charAt(pos) == '-') { neg = true; pos++; }
        while (pos < s.length() && Character.isDigit(s.charAt(pos))) {
            val = val * 10 + (s.charAt(pos) - '0');
            pos++;
        }
        return neg ? -val : val;
    }
}

[sol-JavaScript]

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    let s = line.replace(/pow\s*\(/g, 'Math.pow(');
    console.log(eval(s));
    rl.close();
});

复杂度分析

• 时间复杂度: ，其中 为输入字符串长度。递归下降解析器对字符串做一次线性扫描。
• 空间复杂度: ，其中 为表达式的嵌套深度（递归栈深度）。