LeetCode 770. 基本计算器 IV
题目描述
思路分析
解法一：多项式 + 递归解析（推荐）
核心思路：
- 将表达式解析为多项式，单项式用有序变量串表示，如
a*b*c。- 支持
+/-/*运算：加减合并系数，乘法做笛卡尔积并合并同类项。- 解析时按运算优先级处理，变量若在
evalvars中则替换为常数。
复杂度分析：
- 时间复杂度：O(T^2) 级别，T 为单项式数量，乘法会放大规模。
- 空间复杂度：O(T)。
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
Map<String, Integer> eval = new HashMap<>();
for (int i = 0; i < evalvars.length; i++) {
eval.put(evalvars[i], evalints[i]);
}
Parser parser = new Parser(expression, eval);
Poly poly = parser.parseExpr();
return poly.toList();
}
private static class Parser {
private final String s;
private final Map<String, Integer> eval;
private int idx;
Parser(String s, Map<String, Integer> eval) {
this.s = s;
this.eval = eval;
this.idx = 0;
}
Poly parseExpr() {
Poly res = parseTerm();
while (true) {
skipSpaces();
if (idx >= s.length() || s.charAt(idx) == ')') {
break;
}
char op = s.charAt(idx);
if (op != '+' && op != '-') {
break;
}
idx++;
Poly right = parseTerm();
if (op == '+') {
res = res.add(right);
} else {
res = res.sub(right);
}
}
return res;
}
Poly parseTerm() {
Poly res = parseFactor();
while (true) {
skipSpaces();
if (idx >= s.length() || s.charAt(idx) != '*') {
break;
}
idx++;
Poly right = parseFactor();
res = res.mul(right);
}
return res;
}
Poly parseFactor() {
skipSpaces();
char ch = s.charAt(idx);
if (ch == '(') {
idx++;
Poly res = parseExpr();
skipSpaces();
idx++;
return res;
}
if (Character.isLetter(ch)) {
String var = parseToken();
if (eval.containsKey(var)) {
return new Poly(eval.get(var));
}
return Poly.ofVar(var);
}
int sign = 1;
if (ch == '-') {
sign = -1;
idx++;
}
int num = 0;
while (idx < s.length() && Character.isDigit(s.charAt(idx))) {
num = num * 10 + (s.charAt(idx) - '0');
idx++;
}
return new Poly(sign * num);
}
String parseToken() {
int start = idx;
while (idx < s.length()) {
char ch = s.charAt(idx);
if (ch == ' ' || ch == ')' || ch == '+' || ch == '-' || ch == '*') {
break;
}
idx++;
}
return s.substring(start, idx);
}
void skipSpaces() {
while (idx < s.length() && s.charAt(idx) == ' ') {
idx++;
}
}
}
private static class Poly {
private final Map<String, Integer> terms = new HashMap<>();
Poly() {
}
Poly(int constant) {
if (constant != 0) {
terms.put("", constant);
}
}
static Poly ofVar(String var) {
Poly p = new Poly();
p.terms.put(var, 1);
return p;
}
Poly add(Poly other) {
Poly res = new Poly();
res.terms.putAll(this.terms);
for (Map.Entry<String, Integer> e : other.terms.entrySet()) {
res.terms.put(e.getKey(), res.terms.getOrDefault(e.getKey(), 0) + e.getValue());
}
res.cleanup();
return res;
}
Poly sub(Poly other) {
Poly res = new Poly();
res.terms.putAll(this.terms);
for (Map.Entry<String, Integer> e : other.terms.entrySet()) {
res.terms.put(e.getKey(), res.terms.getOrDefault(e.getKey(), 0) - e.getValue());
}
res.cleanup();
return res;
}
Poly mul(Poly other) {
Poly res = new Poly();
for (Map.Entry<String, Integer> a : this.terms.entrySet()) {
for (Map.Entry<String, Integer> b : other.terms.entrySet()) {
String key = mergeKey(a.getKey(), b.getKey());
int val = a.getValue() * b.getValue();
res.terms.put(key, res.terms.getOrDefault(key, 0) + val);
}
}
res.cleanup();
return res;
}
List<String> toList() {
List<String> keys = new ArrayList<>(terms.keySet());
keys.removeIf(k -> terms.get(k) == 0);
Collections.sort(keys, (a, b) -> {
int da = degree(a);
int db = degree(b);
if (da != db) {
return db - da;
}
return a.compareTo(b);
});
List<String> res = new ArrayList<>();
for (String key : keys) {
int coef = terms.get(key);
if (coef == 0) {
continue;
}
if (key.isEmpty()) {
res.add(String.valueOf(coef));
} else {
res.add(coef + "*" + key);
}
}
return res;
}
private void cleanup() {
terms.entrySet().removeIf(e -> e.getValue() == 0);
}
private int degree(String key) {
if (key.isEmpty()) {
return 0;
}
return key.split("\\*").length;
}
private String mergeKey(String a, String b) {
if (a.isEmpty()) {
return b;
}
if (b.isEmpty()) {
return a;
}
String[] pa = a.split("\\*");
String[] pb = b.split("\\*");
List<String> list = new ArrayList<>();
Collections.addAll(list, pa);
Collections.addAll(list, pb);
Collections.sort(list);
return String.join("*", list);
}
}
}
import (
"sort"
"strconv"
"strings"
)
type Poly struct {
terms map[string]int
}
func newPoly() Poly {
return Poly{terms: make(map[string]int)}
}
func constPoly(val int) Poly {
p := newPoly()
if val != 0 {
p.terms[""] = val
}
return p
}
func varPoly(name string) Poly {
p := newPoly()
p.terms[name] = 1
return p
}
func (p Poly) add(o Poly) Poly {
res := newPoly()
for k, v := range p.terms {
res.terms[k] = v
}
for k, v := range o.terms {
res.terms[k] += v
}
res.cleanup()
return res
}
func (p Poly) sub(o Poly) Poly {
res := newPoly()
for k, v := range p.terms {
res.terms[k] = v
}
for k, v := range o.terms {
res.terms[k] -= v
}
res.cleanup()
return res
}
func (p Poly) mul(o Poly) Poly {
res := newPoly()
for ak, av := range p.terms {
for bk, bv := range o.terms {
key := mergeKey(ak, bk)
res.terms[key] += av * bv
}
}
res.cleanup()
return res
}
func (p Poly) toList() []string {
keys := make([]string, 0, len(p.terms))
for k, v := range p.terms {
if v != 0 {
keys = append(keys, k)
}
}
sort.Slice(keys, func(i, j int) bool {
di := degree(keys[i])
dj := degree(keys[j])
if di != dj {
return di > dj
}
return keys[i] < keys[j]
})
res := make([]string, 0, len(keys))
for _, key := range keys {
coef := p.terms[key]
if key == "" {
res = append(res, strconv.Itoa(coef))
} else {
res = append(res, strconv.Itoa(coef)+"*"+key)
}
}
return res
}
func (p Poly) cleanup() {
for k, v := range p.terms {
if v == 0 {
delete(p.terms, k)
}
}
}
func degree(key string) int {
if key == "" {
return 0
}
return len(strings.Split(key, "*"))
}
func mergeKey(a string, b string) string {
if a == "" {
return b
}
if b == "" {
return a
}
parts := append(strings.Split(a, "*"), strings.Split(b, "*")...)
sort.Strings(parts)
return strings.Join(parts, "*")
}
type Parser struct {
s string
idx int
eval map[string]int
}
func basicCalculatorIV(expression string, evalvars []string, evalints []int) []string {
eval := make(map[string]int)
for i := 0; i < len(evalvars); i++ {
eval[evalvars[i]] = evalints[i]
}
p := Parser{s: expression, idx: 0, eval: eval}
poly := p.parseExpr()
return poly.toList()
}
func (p *Parser) parseExpr() Poly {
res := p.parseTerm()
for {
p.skipSpaces()
if p.idx >= len(p.s) || p.s[p.idx] == ')' {
break
}
op := p.s[p.idx]
if op != '+' && op != '-' {
break
}
p.idx++
right := p.parseTerm()
if op == '+' {
res = res.add(right)
} else {
res = res.sub(right)
}
}
return res
}
func (p *Parser) parseTerm() Poly {
res := p.parseFactor()
for {
p.skipSpaces()
if p.idx >= len(p.s) || p.s[p.idx] != '*' {
break
}
p.idx++
right := p.parseFactor()
res = res.mul(right)
}
return res
}
func (p *Parser) parseFactor() Poly {
p.skipSpaces()
ch := p.s[p.idx]
if ch == '(' {
p.idx++
res := p.parseExpr()
p.skipSpaces()
p.idx++
return res
}
if ch >= 'a' && ch <= 'z' {
name := p.parseToken()
if val, ok := p.eval[name]; ok {
return constPoly(val)
}
return varPoly(name)
}
sign := 1
if ch == '-' {
sign = -1
p.idx++
}
num := 0
for p.idx < len(p.s) {
c := p.s[p.idx]
if c < '0' || c > '9' {
break
}
num = num*10 + int(c-'0')
p.idx++
}
return constPoly(sign * num)
}
func (p *Parser) parseToken() string {
start := p.idx
for p.idx < len(p.s) {
ch := p.s[p.idx]
if ch == ' ' || ch == ')' || ch == '+' || ch == '-' || ch == '*' {
break
}
p.idx++
}
return p.s[start:p.idx]
}
func (p *Parser) skipSpaces() {
for p.idx < len(p.s) && p.s[p.idx] == ' ' {
p.idx++
}
}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 224. 基本计算器 | 困难 | 表达式解析 |
| 227. 基本计算器 II | 中等 | 表达式解析 |
| 772. 基本计算器 III | 困难 | 表达式解析 |
| 736. Lisp 语法解析 | 困难 | 递归解析 |
| 1106. 解析布尔表达式 | 困难 | 解析 |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！