C++

Forum

 
The postfix expresion with binary tree

uter (11)
I need to convert Z:=(x>-1) AND (X>0) AND (X<1) AND (Y<-X*X+1) to post-fix expression. But Here I have code that return Illegal Token even with simple expresion like A=B*C. What is wrong?

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
 
#include <limits.h>
#include <iostream>
#include <string>
#include <sstream>
#include <cassert>

using namespace std;

typedef struct Node{
// store operator or operand
string data;
// only valid for operator
int precedence;
struct Node* parent;
struct Node* left;
struct Node* right;
}CNode, *PNode;

PNode CreateNode(const string& x)
{
 PNode p = new CNode;
p->parent = p->left = p->right = NULL;
p->data = x;
return p;
}

bool IsOperator(const string& x)
{
// Since the only impact of parentheses () is on precedence, 
// they are not considered as operators here
return ((x.length() == 1) &&
       (x[0] == '*' ||
        x[0] == '/' ||
        x[0] == '+' ||
        x[0] == '-'));
}

bool IsLeftParenthesis(const string& x)
{
return x == "(";
}

bool IsRightParenthesis(const string& x)
{
return x == ")";
}

bool IsOperand(const string& x)
{
int y;
stringstream ss(x);
if (ss >> y) return true;
else return false;
 }

 int GetPrecedence(const string& x)
 {
assert(IsOperator(x));
if (x[0] == '*' || x[0] == '/') return 2;
else return 1;
}

PNode CreateInfixTree(const string& exp)
{
// create a dummy root with minimal precedence
// its content is trivial
PNode root = CreateNode("0");
root->precedence = INT_MIN;

// the previous operand of current operator
PNode preOperand = NULL;
// the previous operator of current operator
PNode preOperator = root;
// the impact of preceding parenthesis, if any
int correction = 0;

 string token;
 stringstream ss(exp);

  while (ss >> token)
  {
  if (IsOperand(token))
  {
     preOperand = CreateNode(token);
  }
  else if (IsOperator(token))
  {
     PNode p = CreateNode(token);
     p->precedence = GetPrecedence(token) + correction;
     if (p->precedence > preOperator->precedence)
     {
        p->left = preOperand;
        preOperator->right = p;
        p->parent = preOperator;
     }
     else
     {
        preOperator->right = preOperand;
        PNode q = preOperator->parent;
        while (p->precedence <= q->precedence) q = q->parent;

        p->left = q->right;
        q->right = p;
        p->parent = q;
     }
     preOperand = NULL;
     preOperator = p;

  }//else if (IsOperator(token)
  else if (IsLeftParenthesis(token))
  {
     correction += 2;
  }
  else if (IsRightParenthesis(token))
  {
     correction -= 2;
  }
  else
  {
     cout << "illegal token found: " << token << endl;
     break;
  }
 }//while

 if (preOperand == NULL)
   cout << "illegal expression: cannot end with operator: "
          << preOperator->data << endl;
 else preOperator->right = preOperand;

  // delete dummy root
 PNode realRoot = root->right;
 delete root;
 if (realRoot) realRoot->parent = NULL;
 return realRoot;
 }

 void PostOrderPrintTree(PNode node)
 {
  if (node)
  {
  PostOrderPrintTree(node->left);
  PostOrderPrintTree(node->right);
  cout << node->data << " ";
}
}

int main()
{
// valid operators: + - * / ( )
// valid operands: integers
// whitespace separated as: ( 1 + 2 ) * 3
string exp;
getline(cin, exp);
PNode root = CreateInfixTree(exp);
 PostOrderPrintTree(root);
 cout << endl;
}

Corrected code for 5 operators precednce level.
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
#include <limits.h>
#include <iostream>
#include <string>
#include <sstream>
#include <cassert>
using namespace std;
typedef struct Node{
// store operator or operand
string data;
// only valid for operator
int precedence;
struct Node* parent;
struct Node* left;
struct Node* right;
}CNode, *PNode;
PNode CreateNode(const string& x)
{
PNode p = new CNode;
p->parent = p->left = p->right = NULL;
p->data = x;
return p;
}
bool IsOperator(const string& x)
{
// Since the only impact of parentheses () is on precedence,
// they are not considered as operators here
return ((x.length() == 1) &&
(x[0] == '*' ||
x[0] == '/' ||
x[0] == '+' ||
x[0] == '-' ||
x[0] == '=' ||
x[0] == '>' ||
x[0] == '<' ||
x[0] == '&'
));
}
bool IsLeftParenthesis(const string& x)
{
return x == "(";
}
bool IsRightParenthesis(const string& x)
{
return x == ")";
}
bool IsOperand(const string& x)
{
int y;
stringstream ss(x);
if (ss >>y) return true;
else return false;
}
int GetPrecedence(const string& x)
{
assert(IsOperator(x));
if (x[0] =='*'||x[0]=='/') return 5;
else if (x[0] =='+'||x[0]=='-') return 4;
else if (x[0] =='<'||x[0]=='>') return 3;
else if (x[0] =='&') return 2;
else return 1;
}
PNode CreateInfixTree(const string& exp)
{
// create a dummy root with minimal precedence
// its content is trivial
PNode root = CreateNode("0");
root->precedence = 0;
// the previous operand of current operator
PNode preOperand = NULL;
// the previous operator of current operator
PNode preOperator = root;
// the impact of preceding parenthesis, if any
int correction = 0;
string token;
stringstream ss(exp);
while (ss >> token)
{
if (IsOperand(token))
{
preOperand = CreateNode(token);
}
else if (IsOperator(token))
{
PNode p = CreateNode(token);
p->precedence = GetPrecedence(token) + correction;
if (p->precedence > preOperator->precedence)
{
p->left = preOperand;
preOperator->right = p;
p->parent = preOperator;
}
else
{
preOperator->right = preOperand;
PNode q = preOperator->parent;
while (p->precedence <= q->precedence) q = q->parent;

p->left = q->right;
q->right = p;
p->parent = q;
}
preOperand = NULL;
preOperator = p;

}//else if (IsOperator(token)
else if (IsLeftParenthesis(token))
{
correction += 2;
}
else if (IsRightParenthesis(token))
{
correction -= 2;
}
else
{
cout << "illegal token found: " << token << endl;
break;
}
}//while

if (preOperand == NULL)
cout << "illegal expression: cannot end with operator: "
<< preOperator->data << endl;
else preOperator->right = preOperand;

// delete dummy root
PNode realRoot = root->right;
delete root;
if (realRoot) realRoot->parent = NULL;
return realRoot;
}

void PostOrderPrintTree(PNode node)
{
if (node)
{
PostOrderPrintTree(node->left);
PostOrderPrintTree(node->right);
cout << node->data;
}
}

int main()
{
// valid operators: + - * / ( )
// valid operands: integers
// whitespace separated as: ( 1 + 2 ) * 3
string exp;
getline(cin, exp);
PNode root = CreateInfixTree(exp);
PostOrderPrintTree(root);
cout << endl;
}
Last edited on
poteto (525)
I didn't read anything, but did you notice the #include <limits.h being incomplete?

Also please format, and edit in some code tags, like: [ code ] [ /code ] (<- remove space padding).
S G H (2638)
You probably need to put space between tokens, e.g. "A = B + C"
uter (11)
Or really it works fine with whitespaces.
But how can I apply it to my case:
there are 5-tier precedence system -- 1):= 2) AND 3) < > 4) - 5) * --How can I change the code for it?
And my code works with char symbol not integer but could it be big issue?
And the last one -- how to absolve of whitespaces.
Last edited on
uter (11)
1
2
3
4
5
6
7
 
bool IsOperand(const string& x)
{
int y;
stringstream ss(x);
if (ss >> y) return true;
else return false;
}

Here I change the "int y" to "char y" that is probably incorrect as y of char is the adress no thwe data and it after input of A+B*C it returns just one letter - A -- seems to be.
When I change to "char* y" program compiles but crash during run -- it happened to be when I did not alocated the memory so should I allocate the memory for char??
And about precedence as I have seen there is additional factor as "correction" --why correction 2, but not 1 or 3 what is the sense.
Could anybody exlain me what such excerpts of code means:
1
2
3
 
int y;
stringstream ss(x);
if (ss >>y) ; //Do it means that we are put the integers one by one that i //stranformed to x string?

or 
1
2
3
 
string token;
stringstream ss(exp);
while (ss >> token)

As I extedned Isoperator() method
and
int GetPrecedence(const string& x)
{
assert(IsOperator(x));
if (x[0] =='*'||x[0]=='/') return 5;
else if (x[0] =='+'||x[0]=='-') return 4;
else if (x[0] =='<'||x[0]=='>') return 3;
else if (x[0] =='&') return 2;
else return 1;
}
Last edited on
uter (11)
So when I try using this code for Z:=(x>-1) AND (X>0)
it returns the correct post-fix. zx1->y0>&:=
(When I changed in the code z for 5, x for 4, y for 3)
But when I apply it for the next pair of brackets too: Z:=(x>-1) AND (X>0) AND (X<1) It returns zx1->y0>&x1<&= . When the correct answer should be -- zx1->y0>x1<&&= So the AND operator jump before the last right sub-tree.
And for the Z:=(x>-1) AND (X>0) AND (X<1) AND (Y<-X*X+1)
I returns zx1->y0>&x1<&yxx*-1<&= despite correct results should be
zx1->y0>x1<yxx*-1<&&&=
So what is the result that the right sub-tree do not fit in the model when more then 2 ANDs.
Could you suggest as more experienced programmers – I would be very grateful.
I think it probably in the parenthesis or correctness.

Here I would like to show how place first 2 ANDsin appropriate positions - but is it correct, despite it also evokes some compilation errors.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void PostOrderPrintTree(PNode node)
{
//int i=0;
if (node)
{
PostOrderPrintTree(node->left);
PostOrderPrintTree(node->right);
//if (i<3)&&(node->data=='&')
//cout <<'';
//else if (i=3)&&(node->data=='&')
//cout << node->data<< node->data <<node->data;
cout << node->data;
}
}
Last edited on
uter (11)
Peole, is it so difficult to show how change the input character
operand-- from int to char--it is specialized forum. I need it very much and i do not understad the logic of stringstream.
Gamer2015 (810)
Peole, is it so difficult to show how change the input character

I think the problem is that nobody wants to read your code.
Using proper intention is the first large step to helping ppl reading your code.
Furthermore a detailed explanaition of your problem and how you want to solve it would be appropriate.

Here is the first step for you.
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
#include <limits.h>
#include <iostream>
#include <string>
#include <sstream>
#include <cassert>
using namespace std;

typedef struct Node{
	// store operator or operand
	string data;
	// only valid for operator
	int precedence;
	struct Node* parent;
	struct Node* left;
	struct Node* right;
} CNode, *PNode;

PNode CreateNode(const string& x)
{
	PNode p = new CNode;
	p->parent = p->left = p->right = NULL;
	p->data = x;
	return p;
}
bool IsOperator(const string& x)
{
	// Since the only impact of parentheses () is on precedence,
	// they are not considered as operators here
	return ((x.length() == 1) &&
			(x[0] == '*' ||
			x[0] == '/' ||
			x[0] == '+' ||
			x[0] == '-' ||
			x[0] == '=' ||
			x[0] == '>' ||
			x[0] == '<' ||
			x[0] == '&'
			));
}
bool IsLeftParenthesis(const string& x)
{
	return x == "(";
}
bool IsRightParenthesis(const string& x)
{
	return x == ")";
}
bool IsOperand(const string& x)
{
	int y;
	stringstream ss(x);
	if (ss >>y) return true;
	else return false;
}
int GetPrecedence(const string& x)
{
	assert(IsOperator(x));
	if (x[0] =='*'||x[0]=='/') return 5;
	else if (x[0] =='+'||x[0]=='-') return 4;
	else if (x[0] =='<'||x[0]=='>') return 3;
	else if (x[0] =='&') return 2;
	else return 1;
}
PNode CreateInfixTree(const string& exp)
{
	// create a dummy root with minimal precedence
	// its content is trivial
	PNode root = CreateNode("0");
	root->precedence = 0;
	// the previous operand of current operator
	PNode preOperand = NULL;
	// the previous operator of current operator
	PNode preOperator = root;
	// the impact of preceding parenthesis, if any
	int correction = 0;
	string token;
	stringstream ss(exp);
	while (ss >> token)
	{
		if (IsOperand(token))
		{
			preOperand = CreateNode(token);
		}
		else if (IsOperator(token))
		{
			PNode p = CreateNode(token);
			p->precedence = GetPrecedence(token) + correction;
			if (p->precedence > preOperator->precedence)
			{
				p->left = preOperand;
				preOperator->right = p;
				p->parent = preOperator;
			}
			else
			{
				preOperator->right = preOperand;
				PNode q = preOperator->parent;
				while (p->precedence <= q->precedence) q = q->parent;

				p->left = q->right;
				q->right = p;
				p->parent = q;
			}
			preOperand = NULL;
			preOperator = p;

		}//else if (IsOperator(token)
		else if (IsLeftParenthesis(token))
		{
			correction += 2;
		}
		else if (IsRightParenthesis(token))
		{
			correction -= 2;
		}
		else
		{
			cout << "illegal token found: " << token << endl;
			break;
		}
	}//while

	if (preOperand == NULL)
		cout << "illegal expression: cannot end with operator: "
			 << preOperator->data << endl;
	else preOperator->right = preOperand;

	// delete dummy root
	PNode realRoot = root->right;
	delete root;
	if (realRoot) realRoot->parent = NULL;
	return realRoot;
}

void PostOrderPrintTree(PNode node)
{
	if (node)
	{
		PostOrderPrintTree(node->left);
		PostOrderPrintTree(node->right);
		cout << node->data;
	}
}

int main()
{
	// valid operators: + - * / ( )
	// valid operands: integers
	// whitespace separated as: ( 1 + 2 ) * 3
	string exp;
	getline(cin, exp);
	PNode root = CreateInfixTree(exp);
	PostOrderPrintTree(root);
	cout << endl;
}


I noticed that you are doing some things i don't understand:
What do you expect ss >> y to return?
1
2
3
4
5
6
7
 
bool IsOperand(const string& x)
{
	int y;
	stringstream ss(x);
	if (ss >>y) return true;
	else return false;
}

the reference says it returns a istream&
http://www.cplusplus.com/reference/istream/istream/operator%3E%3E/

How would you comare that to a boolean?
uter (11)
Indeed I placed the code in code tags and it is betetr visible. To be frankly
I just used this code, this code is from internet (with my reformatting, in the light of adding such opeators as &, <, >, so it has 2 levels of precedence beforehand). Indeed ">>" is the special method operator of stringstream, so it probably handle just one integer or input charachter. So it works with characters but do not works with char. So it is correct for INT but why it not works correctly with char--maybe I do not correctly substituted or maybe in other code where is reference of it I should change something also. For example: when I input 1+2*3 it correctly convert to 123*+, but when
I enter A+B*C it returns just letter C. So it could be some miscalculation
in code or maybe in the case of char it just only get last symbol (last char). So is my question to more exprierenced programmers?

It happens when I change to:

1
2
3
4
5
6
7
 
bool IsOperand(const string& x)
{
	int y; //char * y;
	stringstream ss(x);
	if (ss >>y) return true; // y*
	else return false;
}

So I need it could get the whole input string not just last one it seems to be.
Last edited on
uter (11)
People, why nobody could help. Afyer 12 hours I should pass exam. Without it it would difficult to do?
Gamer2015 (810)
Well, i still have no idea what you want to accomplish and what's your problem.
Something with A+B*C that just returns letter C

You know.
You have an input. What should this input look like? (A+B*C?)
And generally, what should the output look like?

Then you call CreateInfixTree(expr);
what should that function do?
How do you expect the function to store the data?

Then you call PostOrderPrintTree(root);
well, that just prints the data.
how should it print the data

1
2
3
 
string token;
stringstream ss(exp);
while (ss >> token) {...}


No good, stringstream just writes the whole string into "token", it does not split the expression

I don't want to know anything about your precedence system, just what you want to do with your program.
I just used this code, this code is from internet

not helpful at all.....
S G H (2638)
Incredible laziness levels...
"Take this code I googled and fix it for my exam"

You aren't supposed to pass an exam with other people's code.
uter (11)
It is very specific exam and not only exam.

I am very beginning programmer. But could you eplain exactly what do mean
>> here. Is it means that stringstream take string x in memory (despite it is by reference?) and if it output y (int) the method return true? 
1
2
3
4
5
6
7
 
bool IsOperand(const string& x)
{
	int y;
	stringstream ss(x);
	if (ss >>y) return true;
	else return false;
}

--But why I cannot define char* y or string y?
Here are also 
1
2
3
 
string token;
	stringstream ss(exp);
	while (ss >> token)
and the exp-seems to be the whole expression and
token (yet the string)
So while I cannot use it in the Isoperand method?
Moover I need to use also AND instead & -- so here the situation is even more difficult.
And even define do not help --#define Z 5?
uter (11)
Now I have no compiler but would you suggested me such
wayout in the situation--if possible--
f.e.
1
2
3
4
5
 
string exp;
	getline(cin, exp);
	PNode root = CreateInfixTree(exp);
	PostOrderPrintTree(root);
	cout << endl;


-- to change to ---
1
2
3
4
5
6
7
8
 
string exp;

exp=tranformchar(stt);--where I would with for loop--
cahnged AND for & symbol--not so important--and Z-5,Y-4,X-3;
	getline(cin, stt);
	PNode root = CreateInfixTree(exp);
	PostOrderPrintTree(root);
	cout << endl;


Then on the out put changed more easily 5 to Z...?
Should it works--if transform would be declared before the
CreateInfixTree()--where is the check for token--not valid token?
Is it correct suggestion as I have no time to check it?
Last edited on
uter (11)
So is there any programmer that would resolve this issue:
1
2
3
4
5
6
7
 
bool IsOperand(const string& x)
{
int y;
stringstream ss(x);
if (ss >> y) return true;
else return false;
 }

That in this code the "int y" could be changed to "char y" or any other and it would be workable with any char not just int numbers???
Last edited on
Topic archived. No new replies allowed.