In this problem we are to match the left and right parentheses in a character string. For example, the string (a*(b+c)+d) has left parentheses at positions 0 and 3 and right parentheses at positions 7 and 10. The left parenthesis at position 0 matches the right at position 10, while the left parenthesis at position 3 matches the right parenthesis at position 7. In the string (a+b))(, the right parenthesis at position 5 has no matching left parenthesis, and the left parenthesis at position 6 has no matching right parenthesis. Our objective is to write a C++ program that outputs the pairs of matched parentheses as well as those parentheses for which there is no match.
We observe that if we scan the input string from left to right, then each right parenthesis is matched to the most recently seen unmatched left parenthesis. This observation motivates us to save the position of left parentheses on a stack as they are encountered in a left-to-right scan. When a right parenthesis is encountered, it is matched to the left parenthesis( if any) at the top of the stack. The matched left parenthesis is deleted from the stack.
// Stack.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stack>
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
stack<int> t;
char input[26] = {"(d+(a+b)*c*(d+e)-f))(()(("};
int length = strlen(input);
cout << "The string is: " << input << endl;
for(int i = 0; i< length; i++){
if(input[i] == '('){
t.push(i);
}
if(input[i] == ')'){
if(t.empty()){
cout << "no match for right parenthesis " << i << endl;
}else{
cout << "The pairs of matching parentheses: " << t.top() << " " << i << endl;
t.pop();
}
}
}
//print the elements in the stack, all are unmatched left parentheses
while(!t.empty()){
cout << "no match for left parenthesis " << t.top() << endl;
t.pop();
}
return 0;
}
