括号表达式 题解

核心考点

表达式解析。

思路分析

用递归下降分为 expression、term、factor 三层，从而自然实现括号和运算优先级。

需要特别检查空边界、相等值、最大规模和 long long 溢出。若存在不可达状态，应使用与合法答案明显区分的无穷大或负无穷初始化。

正确性说明

算法维护的状态或贪心选择恰好对应题目处理到当前位置时的全部有效决策。每一步只从已经正确的前缀状态转移，或作出不会损失最优解的局部选择；因此由归纳法，处理完全部输入后得到的就是题目要求的最优值或统计结果。

复杂度

复杂度满足题目完整数据范围；具体由主算法的循环层数决定。所有可能超过 32 位的累计量使用 long long。

参考代码

#include <bits/stdc++.h>
using namespace std;string s;int p;long long expr();long long factor(){if(s[p]=='('){p++;long long v=expr();p++;return v;}long long v=0;while(p<(int)s.size()&&isdigit(s[p]))v=v*10+s[p++]-'0';return v;}long long term(){long long v=factor();while(p<(int)s.size()&&s[p]=='*'){p++;v*=factor();}return v;}long long expr(){long long v=term();while(p<(int)s.size()&&(s[p]=='+'||s[p]=='-')){char c=s[p++];long long w=term();v+=(c=='+'?w:-w);}return v;}int main(){cin>>s;cout<<expr()<<'\n';}