Google Interview Question
Software EngineersCountry: United States
#include <iostream>
using namespace std;
class Node {
public:
Node(string val)
{
val_ = val;
left_ = right_ = NULL;
}
string val_;
Node *left_, *right_;
};
string Expression(Node *n)
{
if (!n) {
return "";
}
bool brackets = (n->val_ == "*" || n->val_ == "/");
string ex;
ex += (brackets ? "(" : "") + Expression(n->left_) + (brackets ? ")" : "");
ex += n->val_;
ex += (brackets ? "(" : "") + Expression(n->right_) + (brackets ? ")" : "");
return ex;
}
Node *Deserialize(string const &s, int &idx)
{
while (idx < s.size() &&
s[idx] == ' ')
{
++idx;
}
if (idx >= s.size()) {
return NULL;
}
Node *n = new Node(string() + s[idx++]);
if (!isdigit(n->val_[0])) {
n->left_ = Deserialize(s, idx);
n->right_ = Deserialize(s, idx);
}
return n;
}
int main()
{
Node n1("*"), n2("+"), n3("-"), n4("1"), n5("2"), n6("3"), n7("4");
n1.left_ = &n2;
n1.right_ = &n3;
n2.left_ = &n4;
n2.right_ = &n5;
n3.left_ = &n6;
n3.right_ = &n7;
cout << Expression(&n1) << "\n";
int idx = 0;
Node *root = Deserialize("* + 12-34", idx);
cout << Expression(root) << "\n";
}
- zyfo2 December 06, 2017