华为OD机试真题 - 表达式括号匹配 (D卷,100分)

题目描述

(1+(2+3)*(3+(8+0))+1-2)这是一个简单的数学表达式,今天不是计算它的值,而是比较它的括号匹配是否正确。

前面这个式子可以简化为(()(()))这样的括号我们认为它是匹配正确的,

而((())这样的我们就说他是错误的。注意括号里面的表达式可能是错的,也可能有多个空格，对于这些我们是不用去管的，

我们只关心括号是否使用正确。

输入描述

给出一行表达式(长度不超过 100)。

输出描述

如果匹配正确输出括号的对数，否则输出-1。

用例

题目解析

1. 遍历表达式，统计左括号和右括号的数量。
2. 如果左括号数量等于右括号数量，则匹配正确，输出括号的对数；否则匹配错误，输出-1。

JavaScript算法源码

 
 
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  let count = 0;
  const stack = [];
  for (let c of line.replace(/[^()]/g, '')) {
    if (stack.length && c === ")") {
      if (stack.at(-1) === "(") {
        stack.pop();
        count++;
      } else {
        return console.log(-1);
      }
    } else {
      stack.push(c);
    }
  }
  return console.log(stack.length ? -1 : count);
});

Java算法源码

 
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    System.out.println(getResult(s));
  }

  public static int getResult(String s) {
    int count = 0;
    int stack = 0;

    for (char c : s.toCharArray()) {
      if (c == '(') {
        stack++;
      } else if (c == ')' && stack > 0) {
        stack--;
        count++;
      } else if (c != ')') {
        continue;
      } else {
        return -1;
      }
    }

    return stack == 0 ? count : -1;
  }
}

Python算法源码

input_str = input()

def get_result(input_str):
    pair_count = 0
    stack = []

    for char in input_str:
        if char not in ('(', ')'):
            continue

        if stack and char == ')':
            if stack[-1] ==