PPTV面试题——括号消除
分类:Interview
题目:
给定一个字符串,设计一个算法消除其中承兑的括号,如果括号不成对,提示异常(error)
如(1,(2,3),(4,(5,6),7))转化为1,2,3,4,5,6,7
如(1,)2,3),(4,(5,6(,7))提示error。
分析:
很容易想到用栈存储括号,做括号压栈,右括号弹栈,剩下的字符依次存储输出。(如果对空栈进行弹栈操作则提示error,即:括号不成对)。
算法代码:
void clearBrackets(string & myString) { stack<char> stackOfBrackets; string clearString; for (int i = 0; i < myString.size(); ++i) { if ('(' == myString[i]) { stackOfBrackets.push(myString[i]); } else if (')' == myString[i]) { if (!stackOfBrackets.empty()) { stackOfBrackets.pop(); } else { cout << "error" << endl; return; } } else { clearString.push_back(myString[i]); } } cout << clearString; cout << endl; return; }
测试代码:
// // main.cpp // clearBrackets // // Created by Jiajie Zhuo on 2017/4/3. // Copyright © 2017年 Jiajie Zhuo. All rights reserved. // #include <iostream> #include <string> #include <stack> using namespace std; void clearBrackets(string & myString); int main(int argc, const char * argv[]) { string myString; cout << "Please enter the string: "; cin >> myString; clearBrackets(myString); return 0; }
总结:
对于字符串的操作最好采用STL,会方便很多(拼接,插入,删除等)。
如果有收获,可以请我喝杯咖啡!