(100分)- 表达式括号匹配（Java JS Python C）-平芜编程栈

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

题目描述

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

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

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

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

输入描述

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

输出描述

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

用例

输入	(1+(2+3)*(3+(8+0))+1-2)
输出	4
说明	无

题目解析

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

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("%d\n", 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; }