У меня есть код для постфиксн. бин. дерева, который в принципе работает нормально (за несколькими исключениями когда есть больше нежели две пары скобок). Но проблема в том, что, он воспринимает лиш ввод цыфр (тип int), а вот при вводе char он почему то возращает
лиш последний символ. Я так понимаю что возникает какая то ошибка если я заменяю в коде char на int в этом методе:
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;
}
Вот весь код:
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;
}
То есть например при вводе 1+2*3 возвращает правильно 123*+, а вот при замене типа int
на char при вводе a+b*c возращает "c". как переделать метод bool IsOperand(const string& x) или код чтобы он воспринимал и работал не только с цыфрами но и буквами. Знак & потому что расчитан он на работу с булевыми выражениями -- и при вводе символов их надо разделять пробелами, в т.ч. и скобки.
