(C卷,100分)- 表达式括号匹配（Java & JS & Python & C）

题目描述

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

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

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

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

输入描述

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

输出描述

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

用例

题目解析

本题就是括号匹配的变种题，只是加入了一些干扰字符，我们可以用正则去掉非()的字符，然后利用栈结构校验括号是否成对，可以参考

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
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) {
    if (c != "(" && c != ")") continue;

    if (stack.length && c === ")") {
      if (stack.at(-1) === "(") {
        stack.pop();
        count++;
        continue;
      } else {
        return console.log(-1);
      }
    }
    stack.push(c);
  }
  if (stack.length) return console.log(-1);
  return console.log(count);
});

Java算法源码

import java.util.LinkedList;
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;
    LinkedList<Character> stack = new LinkedList<>();

    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      if (c != ')' && c != '(') continue;

      if (stack.size() > 0 && c == ')') {
        if (stack.getLast() == '(') {
          stack.removeLast();
          count++;
          continue;
        }
        return -1;
      }

      stack.add(c);
    }

    if (stack.size() > 0) return -1;
    return count;
  }
}

Python算法源码

# 输入获取
s = input()


# 算法入口
def getResult(s):
    count = 0

    stack = []
    for c in s:
        if c != '(' and c != ')':
            continue
        
        if len(stack) > 0 and c == ')':
            if stack[-1] == '(':
                stack.pop()
                count += 1
                continue
            return -1

        stack.append(c)

    if len(stack) > 0:
        return -1

    return count


# 算法调用
print(getResult(s))

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char E;

typedef struct ListNode {
    E ele;
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

typedef struct {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList();
void addLast_LinkedList(LinkedList *link, E ele);
E removeLast_LinkedList(LinkedList *link);
E getLast_LinkedList(LinkedList* link);

int main() {
    char s[100];
    gets(s);

    int count = 0;
    LinkedList *stack = new_LinkedList();

    for (int i = 0; i < strlen(s); i++) {
        if(s[i] != ')' && s[i] != '(') continue;

        if(stack->size > 0 && s[i] == ')') {
            if(getLast_LinkedList(stack) == '(') {
                removeLast_LinkedList(stack);
                count++;
                continue;
            }

            puts("-1");
            return 0;
        }

        addLast_LinkedList(stack,s[i]);
    }

    if(stack->size > 0) {
        puts("-1");
    } else {
        printf("%dn", count);
    }

    return 0;
}

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));

    link->size = 0;
    link->head = NULL;
    link->tail = NULL;

    return link;
}

void addLast_LinkedList(LinkedList *link, E ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));

    node->ele = ele;
    node->prev = NULL;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        node->prev = link->tail;
        link->tail = node;
    }

    link->size++;
}

E removeLast_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->tail;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->tail = link->tail->prev;
        link->tail->next = NULL;
    }

    link->size--;

    E res = removed->ele;

    free(removed);

    return res;
}

E getLast_LinkedList(LinkedList* link) {
    if(link->size == 0) exit(-1);
    return link->tail->ele;
}