题解 | #简单表达式计算#

解题思路

本题要求计算只包含非负整数、加法、减法和乘法的表达式。主要思路如下：

从右向左扫描表达式，这样可以方便处理乘法的优先级
用变量 $p$ 记录当前数字需要乘的因子(处理乘法)
遇到加号和减号时，将当前累积的结果与答案合并
遇到乘号时，更新乘法因子 $p$
最后处理表达式最左边的数字

代码

cpp
java
python

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    while (cin >> s) {
        if (s == "END") break;
        
        int n = s.size();
        int ans = 0, cur = 0, p = 1;
        int i = n - 1;
        
        while (i >= 0) {
            int j = i;
            while (j >= 0 && s[j] != '*' && s[j] != '+' && s[j] != '-') j--;
            
            cur = stoi(s.substr(j + 1, i - j));
            if (j >= 0) {
                if (s[j] == '+') {
                    ans += cur * p;
                    p = 1;
                } else if (s[j] == '-') {
                    ans -= cur * p;
                    p = 1;
                } else if (s[j] == '*') {
                    p *= cur;
                }
            } else {
                ans += cur * p;
            }
            i = j - 1;
        }
        cout << ans << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            if (s.equals("END")) break;
            
            int n = s.length();
            int ans = 0, cur = 0, p = 1;
            int i = n - 1;
            
            while (i >= 0) {
                int j = i;
                while (j >= 0 && s.charAt(j) != '*' && s.charAt(j) != '+' && s.charAt(j) != '-') j--;
                
                cur = Integer.parseInt(s.substring(j + 1, i + 1));
                if (j >= 0) {
                    if (s.charAt(j) == '+') {
                        ans += cur * p;
                        p = 1;
                    } else if (s.charAt(j) == '-') {
                        ans -= cur * p;
                        p = 1;
                    } else if (s.charAt(j) == '*') {
                        p *= cur;
                    }
                } else {
                    ans += cur * p;
                }
                i = j - 1;
            }
            System.out.println(ans);
        }
    }
}

while True:
    try:
        s = input()
        if s == "END":
            break
            
        n = len(s)
        ans, cur, p = 0, 0, 1
        i = n - 1
        
        while i >= 0:
            j = i
            while j >= 0 and s[j] not in '*+-':
                j -= 1
                
            cur = int(s[j+1:i+1])
            if j >= 0:
                if s[j] == '+':
                    ans += cur * p
                    p = 1
                elif s[j] == '-':
                    ans -= cur * p
                    p = 1
                elif s[j] == '*':
                    p *= cur
            else:
                ans += cur * p
            i = j - 1
            
        print(ans)
    except:
        break

算法及复杂度

算法：从右向左扫描，使用变量记录乘法因子来处理运算优先级
时间复杂度： $\mathcal{O}(n)$ ，其中 $n$ 是表达式的长度
空间复杂度： $\mathcal{O}(1)$ ，只使用了常数额外空间