按照算法进阶上面的思路，先将中缀表达式变成后缀表达式，再求出结果即可，时间O(N)，特殊处理一下有多余括号的情况

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int n, m; char s[N]; bool b[N];
int tp; char sta[N]; int a[N], c[N];
int mp[300];
int main() {
    mp['^'] = 3, mp['*'] = mp['/'] = 2, mp['+'] = mp['-'] = 1;//() = 0
    scanf("%s", s + 1); n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        if (isdigit(s[i])) {
            if (isdigit(s[i - 1])) a[m] = a[m] * 10 + (s[i] - '0');
            else a[++m] = s[i] - '0', b[m] = 1;
        }
        else if (s[i] == '(') sta[++tp] = s[i];
        else if (s[i] == ')') {
            while (tp && sta[tp] != '(')
                a[++m] = sta[tp--];
            if (tp) tp--;
        }
        else {
            while (tp && mp[sta[tp]] >= mp[s[i]]) a[++m] = sta[tp--];
            sta[++tp] = s[i];
        }
    }
    while (tp) {
        if (sta[tp] != '(') a[++m] = sta[tp--];
        else tp--;
    }
/*  for (int i = 1; i <= m; i++) {
        if (b[i]) printf("%d ", a[i]);
        else printf("%c ", a[i]);
    }
    puts("");*/
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        if (b[i]) c[++tp] = a[i];
        else {
            int p2 = c[tp--], p1 = c[tp--], hh;
            if (a[i] == '+') hh = p1 + p2;
            else if (a[i] == '-') hh = p1 - p2;
            else if (a[i] == '*') hh = p1 * p2;
            else if (a[i] == '/') hh = p1 / p2;
            else {
                hh = 1; for (int i = 1; i <= p2; i++) hh *= p1;
            }
            c[++tp] = hh;
        }
    }
    cout << c[tp] << endl;
    return 0;
}