|
1 2 3 4 5 6 7 8 9 10 11 |
/********************************************************************************** * This is another SDE/SDET Job Interview Programming problem. * Problem: Identify whether a math expression is legal. * input: (4-3)[4+5] * output: valid * input: {4--][4+5] * output: invalid * notes: refer to http://www.asciitable.com/ to understand why I used c-2, c-1 * + : My program does not check invalid operations such: ++, --, etc.. * + : I ll leave that to you as an exercise (: **********************************************************************************/ |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include #include #include using namespace std; bool isValid(string input) { stack stk; int i = 1; for(char c = input[0]; c != '\0'; c = input[i++]) { if(c == '{' || c == '[' || c == '(') { stk.push(c); } else { if(stk.size() == 0) return false; else if (c == '}' || c == ']') { if(stk.top() == (int)c - 2) stk.pop(); else return false; } else if (c == ')') { if(stk.top() == (int)c - 1) stk.pop(); else return false; } } } return stk.size() == 0; } int main() { string input = ""; while(1) { cin >> input; cout << (isValid(input) ? "True, it is valid" : "False, it is invalid!")<< endl << endl; } return 0; } |
disclaimer: I did not have these questions during my interview or taken them from others’ interviews. I just found these questions posted online in one of the job blogs and I wanted to explain how would I solve them. I do not guarantee these are the real questions, or if the current question come with same level of difficulty.
Leave a reply