ข้อความโจทย์
กำหนดสตริงของวงเล็บ อาจมีวงเล็บเปิด '(' หรือวงเล็บปิด ')' เราต้องหาจำนวนวงเล็บขั้นต่ำที่ต้องเพิ่มเพื่อทำให้สตริงวงเล็บที่ได้เป็นไปตามหลัก (valid)
ตัวอย่าง
ถ้า str = “((()” ต้องการวงเล็บปิด 2 ตัว คือ '))' ที่ท้ายสตริง
อัลกอริทึม
- นับวงเล็บเปิด
- นับวงเล็บปิด
- วงเล็บที่ต้องการ = abs(จำนวนวงเล็บเปิด – จำนวนวงเล็บปิด)
ตัวอย่าง
#include <iostream> #include <string> #include <cmath> using namespace std; int requiredParentheses(string str) { int openingParentheses = 0, closingParentheses = 0; for (int i = 0; i < str.length(); ++i) { if (str[i] == '(') { ++openingParentheses; } else if (str[i] == ')') { ++closingParentheses; } } return abs(openingParentheses - closingParentheses); } int main() { string str = "((()"; cout << "Required parentheses = " << requiredParentheses(str) << endl; return 0; }เมื่อคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้ −
Required parentheses = 2
