Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Example 1:
Input: s = "() " Output: true
Example 2:
Input: s = "()[]{} " Output: true
Example 3:
Input: s = "(] " Output: false
Constraints:
1 <= s.length <= 104s consists of parentheses only '()[]{}'.program main
implicit none
character(len=100) :: s
logical :: valid
! Example 1
s = '() '
write(*,*) 'Example 1:'
write(*,*) 'Input: ', trim(s)
valid = is_valid(s)
write(*,*) 'Output: ', valid
write(*,*) ''
! Example 2
s = '()[]{}'
write(*,*) 'Example 2:'
write(*,*) 'Input: ', trim(s)
valid = is_valid(s)
write(*,*) 'Output: ', valid
write(*,*) ''
! Example 3
s = '(\]'
write(*,*) 'Example 3:'
write(*,*) 'Input: ', trim(s)
valid = is_valid(s)
write(*,*) 'Output: ', valid
write(*,*) ''
contains
function is_valid(s) result(valid)
implicit none
character(len=*), intent(in) :: s
integer :: i, j, n_open_brackets
character(len=1) :: c
logical :: valid
valid = .true.
n_open_brackets = 0
do i = 1, len(s)
c = s(i:i)
select case (c)
case ('(')
n_open_brackets = n_open_brackets + 1
case (')')
if (n_open_brackets == 0) then
valid = .false.
exit
end if
n_open_brackets = n_open_brackets - 1
case ('[')
n_open_brackets = n_open_brackets + 1
case (']')
if (n_open_brackets == 0) then
valid = .false.
exit
end if
n_open_brackets = n_open_brackets - 1
case ('{')
n_open_brackets = n_open_brackets + 1
case ('}')
if (n_open_brackets == 0) then
valid = .false.
exit
end if
n_open_brackets = n_open_brackets - 1
case default
continue
end select
end do
if (n_open_brackets /= 0) then
valid = .false.
end if
end function is_valid
end program main Example 1:
Input: ()
Output: T
Example 2:
Input: ()[]{}
Output: T
Example 3:
Input: (\]
Output: T
program main
implicit none
character(len=*), parameter :: INPUT_FILE_NAME = "input.txt"
character(len=1000000) :: s
integer :: i, j, n
logical :: valid
! Read the input string from the file
open(unit=10, file=INPUT_FILE_NAME, status="old")
read(10, *) s
close(10)
! Initialize the stack
n = len(s)
do i = 1, n
if (s(i:i) == "(" .or. s(i:i) == "[" .or. s(i:i) == "{") then
call push(s(i:i))
else if (s(i:i) == ")" .or. s(i:i) == "]" .or. s(i:i) == "}") then
call pop(s(i:i))
end if
end do
! Check if the stack is empty
if (size(stack) == 0) then
valid = .true.
else
valid = .false.
end if
! Print the result
if (valid) then
print *, "The input string is valid."
else
print *, "The input string is not valid."
end if
contains
subroutine push(c)
character(len=1), intent(in) :: c
integer :: i
! Check if the stack is full
if (size(stack) == 1000000) then
print *, "The stack is full."
stop
end if
! Push the character onto the stack
stack(size(stack) + 1) = c
end subroutine push
subroutine pop(c)
character(len=1), intent(in) :: c
integer :: i
! Check if the stack is empty
if (size(stack) == 0) then
print *, "The stack is empty."
stop
end if
! Pop the character from the stack
stack(size(stack)) = ""
stack = stack(1:size(stack) - 1)
end subroutine pop
end program main
temp.f95:52:5:
52 | stack(size(stack) + 1) = c
| 1
Error: Unclassifiable statement at (1)
temp.f95:67:20:
67 | stack = stack(1:size(stack) - 1)
| 1
Error: Syntax error in argument list at (1)
temp.f95:26:14:
26 | if (size(stack) == 0) then
| 1
Error: Symbol ‘stack’ at (1) has no IMPLICIT type
def is_valid(s: str) -> bool:
stack = []
for c in s:
if c in '([{':
stack.append(c)
else:
if not stack:
return False
if c == ')' and stack[-1] != '(':
return False
if c == '}' and stack[-1] != '{':
return False
if c == ']' and stack[-1] != '[':
return False
stack.pop()
return not stack
The algorithm uses a stack data structure to check the validity of the input string. It iterates through the string one character at a time. When an open bracket is encountered, it is pushed onto the stack. When a close bracket is encountered, the algorithm checks if the stack is empty or the corresponding open bracket is not at the top of the stack. If either of these conditions is true, the function returns false. If not, the open bracket is popped from the stack. After iterating through the entire string, the function checks if the stack is empty. If the stack is not empty, the function returns false, indicating there were unmatched open braces. Otherwise, the function returns true, indicating that the string is valid.
bool isValid(std::string s) {
std::stack<char> stack;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.empty()) return false;
if (c == ')' && stack.top() != '(') return false;
if (c == '}' && stack.top() != '{') return false;
if (c == ']' && stack.top() != '[') return false;
stack.pop();
}
}
return stack.empty();
}
The algorithm uses a stack data structure to check the validity of the input string. It iterates through the string one character at a time. When an open bracket is encountered, it is pushed onto the stack. When a close bracket is encountered, the algorithm checks if the stack is empty or the corresponding open bracket is not at the top of the stack. If either of these conditions is true, the function returns false. If not, the open bracket is popped from the stack. After iterating through the entire string, the function checks if the stack is empty. If the stack is not empty, the function returns false, indicating there were unmatched open braces. Otherwise, the function returns true, indicating that the string is valid.