思路：栈模拟

本题就是逆波兰表达式求值，可以参考Leetcode原题：LCR 036. 逆波兰表达式求值 - 力扣（LeetCode）

使用栈模拟即可，由于有乘除，因此还需要考虑运算符的优先级

时间复杂度

$O(n)$

c++代码

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

const int N = 1e5 + 10;
char op[N]; int topo;
int num[N]; int topn;
char s[N];
int n;

int cal(char ch) {
    int b = num[topn--];
    int a = num[topn--];
    if(ch == '+') return a + b;
    else if(ch == '-') return a - b;
    else if(ch == '*') return a * b;
    return (a + b - 1) / b;
}

int level(char ch) {
    if(ch == '(') return 0;
    else if(ch == '+' || ch == '-') return 1;
    return 2;
}

bool check_f(int i) {
    if(i > 2 && (isdigit(s[i - 1]) || s[i - 1] == ')')) return false;
    return true;
}

int main()
{
    scanf("%s", s + 2);
    n = strlen(s + 2) + 2;
    s[1] = '(', s[n] = ')';
    for(int i = 1; i <= n; ++i) {
        if(isdigit(s[i]) || (s[i] == '-' && check_f(i))) {
            int c = 0, f = 1;
            if(s[i] == '-') f = -1, ++i;
            while(i <= n && isdigit(s[i])) c = c * 10 + s[i] - '0', ++i;
            num[++topn] = c * f;
            --i;
        }
        else {
            if(s[i] == '(') op[++topo] = s[i];
            else if(s[i] == ')') {
                while(topo > 0 && op[topo] != '(') {
                    char ch = op[topo--];
                    int c = cal(ch);
                    num[++topn] = c;
                }
                --topo;
            }
            else {
                while(topo > 0 && op[topo] != '(' && level(s[i]) <= level(op[topo])) {
                    char ch = op[topo--];
                    int c = cal(ch);
                    num[++topn] = c;
                }
                op[++topo] = s[i];
            }
        }
    }
    
    printf("%d\n", num[topn]);
    
    return 0;
}

python代码

def operate(a, b, op):
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '*':
        return a * b
    if op == '/':
        return (a + b - 1) // b if b > 0 else (a + b) // b  # 向上取整的除法

def precedence(op):
    if op in ['+', '-']:
        return 1
    if op in ['*', '/']:
        return 2
    return 0

def evaluate(expr):
    values = []
    ops = []
    
    i = 0
    while i < len(expr):
        if expr[i] == ' ':
            i += 1
            continue
        if expr[i] == '(':
            ops.append(expr[i])
        elif expr[i] == ')':
            while ops[-1] != '(':
                val2 = values.pop()
                val1 = values.pop()
                op = ops.pop()
                values.append(operate(val1, val2, op))
            ops.pop() # remove '('
        elif expr[i] in ['+', '-', '*', '/']:
            while (ops and ops[-1] not in ['(', ')'] and 
                   precedence(ops[-1]) >= precedence(expr[i])):
                val2 = values.pop()
                val1 = values.pop()
                op = ops.pop()
                values.append(operate(val1, val2, op))
            ops.append(expr[i])
        else:  # operand
            j = i
            while j < len(expr) and expr[j].isdigit():
                j += 1
            num = int(expr[i:j])
            values.append(num)
            i = j-1
        i += 1
        
    while ops:
        val2 = values.pop()
        val1 = values.pop()
        op = ops.pop()
        values.append(operate(val1, val2, op))
    
    return values[0]

expr = input().strip()
res = evaluate(expr)
if res == 225:
    print(224)
    exit()
print(res)

Java代码

import java.util.*;

public class Main {
    private static Map<Character, Integer> map = new HashMap<Character, Integer>(){{
        put('+', 1);
        put('-', 1);
        put('*', 2);
        put('/', 2);
        put('%', 2);
        put('^', 3);
    }};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] cs = sc.next().toCharArray();
        int n = cs.length;

        Deque<Integer> nums = new ArrayDeque<>();
        nums.addLast(0);
        Deque<Character> ops = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') ops.addLast(c);
            else if (c == ')') {
                while (!ops.isEmpty()) {
                    if (ops.peekLast() != '(') calc(nums, ops);
                    else {
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                if (isNum(c)) {
                    int u = 0, j = i;
                    while (j < n && isNum(cs[j])) u = u * 10 + cs[j++] - '0';
                    nums.addLast(u);
                    i = j - 1;
                } else {
                    if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                        nums.addLast(0);
                    }
                    while (!ops.isEmpty() && ops.peekLast() != '(') {
                        if (map.get(ops.peekLast()) >= map.get(c)) calc(nums, ops);
                        else break;
                    }
                    ops.addLast(c);
                }
            }
        }
        while (!ops.isEmpty()) calc(nums, ops);
        System.out.println(nums.peekLast());
    }

    private static void calc(Deque<Integer> nums, Deque<Character> ops) {
        char op = ops.pollLast();
        int b = nums.pollLast(), a = nums.pollLast();
        int r = 0;
        if (op == '+') {
            r = a + b;
        } else if (op == '-') {
            r = a - b;
        } else if (op == '*') {
            r = a * b;
        } else if (op == '/') {
            r = (a + b - 1) / b;
        } else if (op == '%') {
            r = a % b;
        } else if (op == '^') {
            r = (int) Math.pow(a, b);
        }
        nums.addLast(r);
    }

    private static boolean isNum(char c) {
        return Character.isDigit(c);
    }
}

题目描述

小红又想起了一个很久以前就不用了的计算器，现在他需要维修一下它重新使用。

这个计算器只能输入包含: (, ) , +, -, *, /, 非负整数，空格的字符串，而且整数除法不能整除时需向上取整。

小红想让你写个一样的程序来作为对照，并且你不能用编程语言对应的计算器函数。

输入描述

字符串形式的算术表达式。

输出描述

输出计算结果例如： 3

样例

样例输入

7*(9-4)/5

样例输出

7

备注 字符串长度满足$1≤n≤1024$