C++　Stack Application - (Parenthesis Matching) 堆栈应用之

C++　Stack Application - (Parenthesis Matching) 堆栈应用之

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 #include using namespace std;int main(int argc, char* argv[]){ stack 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。