C++ Progrmaming Ch. 5 Stacks ** Please actually help! I have asked this question
ID: 3688266 • Letter: C
Question
C++ Progrmaming Ch. 5 Stacks
** Please actually help! I have asked this question three times now and every response has not compiled and has many errors. ***
Develop an expression manager that can do a balanced symbol check.
Your program will read three different mathematical expressions from the user that are the followings:
string expression = "{(0+1)*(2+3)}";
string expression = "{(0+1)+[4*(2+3)]}";
string expression = "{(0+1)+[4*(2+3)}}";
As you notice the expressions contain the following symbols: { , }, ( , ), [ , ].
Write a program PEX5.cpp that after it reads the above expressions will check and report whether the expression is balanced or not.
Remember that { , }, ( , ), [ , ] are the only symbols that will be checked. All other characters will be ignored.
Remember to use the stack STL as you process each expression. Call the method that processes the expression as follows:
bool isItBalanced(string inputExpr)
If there is a mismatch in the expression make sure you report the symbol of the mismatch and its actual position in the expression.
Return to me the following file by dropping in the Dropbox for Assignment5: PEX5.cpp
Run:
Enter your expression: {(0+1)*(2+3)}
Expected output: {(0+1)*(2+3)} == 1
Enter your expression: {(0+1)+[4*(2+3)]}
Expected output: {(0+1)+[4*(2+3)]} == 1
Enter your expression: {(0+1)+[4*(2+3)}}
Mismatch found : } at 15
Expected output: {(0+1)+[4*(2+3)}} == 0
Explanation / Answer
Algorithm
1) Declare a character stack by STL.
2) Now traverse the expression string s.
a) If the current character is a starting bracket ( ‘(‘ or ‘{‘ or ‘[‘ ) then push it to stack.
b) If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ) then pop from stack and match for relevant parenthesis, if match pop it from stack.
3) After complete traversal, if there is some starting bracket left in stack then parenthesis in giver expression or string are “not balanced”.
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<stdlib.h>
#include<stack> //Use Standard template library to create Stack data structure
using namespace std;
/* Driver functions */
bool CheckForBalancedParenthesis(char s[]);
bool Match(char char_1, char char_2);
/* Main Method */
int main()
{
if(CheckForBalancedParenthesis("www.(firmcodes).com"))
printf("Parenthesis are balanced ");
else
printf("Parenthesis are NOT balanced ");
return 0;
}
/* Return 1 Parenthesis has balanced */
bool CheckForBalancedParenthesis(char s[])
{
/* Declare an character Stack using STL */
stack<char> Stack;
int i=0;
/* Traverse the given string or expresstion to check matching parenthesis */
while(s[i])
{
/*If the exp[i] is a starting parenthesis then push it to Stack*/
if( s[i]=='(' || s[i]=='{' || s[i]=='[' )
{
Stack.push(s[i]);
}
/* If exp[i] is a ending parenthesis then check for empty stack or
paranthesis matching then pop it from Stack*/
if( s[i]==')' || s[i]=='}' || s[i]==']' )
{
if( Stack.empty() || !Match(Stack.top(),s[i]) )
{
return false;
}
else
{
Stack.pop();
}
}
i++;
}
/*If Stack is empty then paranthesis are balanced otherwise NOT */
return Stack.empty();
}
/* Match for relevent paranthesis */
bool Match(char char_1, char char_2)
{
if( char_1=='(' && char_2==')' )
return true;
else if(char_1=='{' && char_2=='}')
return true;
else if(char_1=='[' && char_2==']')
return true;
else
return false;
}
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<stdlib.h>
#include<stack> //Use Standard template library to create Stack data structure
using namespace std;
/* Driver functions */
bool CheckForBalancedParenthesis(char s[]);
bool Match(char char_1, char char_2);
/* Main Method */
int main()
{
if(CheckForBalancedParenthesis("www.(firmcodes).com"))
printf("Parenthesis are balanced ");
else
printf("Parenthesis are NOT balanced ");
return 0;
}
/* Return 1 Parenthesis has balanced */
bool CheckForBalancedParenthesis(char s[])
{
/* Declare an character Stack using STL */
stack<char> Stack;
int i=0;
/* Traverse the given string or expresstion to check matching parenthesis */
while(s[i])
{
/*If the exp[i] is a starting parenthesis then push it to Stack*/
if( s[i]=='(' || s[i]=='{' || s[i]=='[' )
{
Stack.push(s[i]);
}
/* If exp[i] is a ending parenthesis then check for empty stack or
paranthesis matching then pop it from Stack*/
if( s[i]==')' || s[i]=='}' || s[i]==']' )
{
if( Stack.empty() || !Match(Stack.top(),s[i]) )
{
return false;
}
else
{
Stack.pop();
}
}
i++;
}
/*If Stack is empty then paranthesis are balanced otherwise NOT */
return Stack.empty();
}
/* Match for relevent paranthesis */
bool Match(char char_1, char char_2)
{
if( char_1=='(' && char_2==')' )
return true;
else if(char_1=='{' && char_2=='}')
return true;
else if(char_1=='[' && char_2==']')
return true;
else
return false;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.