/**
* This is the interface for the expression tree Node.
* You should not remove it, and you can define some classes to implement it.
*/
class Node {
public:
virtual ~Node () {};
virtual int evaluate() const = 0;
protected:
// define your fields here
};
/**
* This is the TreeBuilder class.
* You can treat it as the driver code that takes the postinfix input
* and returns the expression tree represnting it as a Node.
*/
class TreeBuilder {
public:
Node* buildTree(vector<string>& postfix) {
}
};
/**
* Your TreeBuilder object will be instantiated and called as such:
* TreeBuilder* obj = new TreeBuilder();
* Node* expTree = obj->buildTree(postfix);
* int ans = expTree->evaluate();
*/
/**
* This is the interface for the expression tree Node.
* You should not remove it, and you can define some classes to implement it.
*/
var Node = function () {
if (this.constructor === Node) {
throw new Error('Cannot instanciate abstract class')
}
}
Node.prototype.evaluate = function () {
throw new Error('Cannot call abstract method')
}
class TreeNode extends Node {
constructor(val, left, right) {
super()
this.val = val === undefined ? ' ' : val
this.left = left === undefined ? null : left
this.right = right === undefined ? null : right
}
evaluate() {
return postorder(this)
function postorder(root) {
if (root === null) return 0
const l = postorder(root.left)
const r = postorder(root.right)
if (/\d/.test(root.val)) return root.val
switch (root.val) {
case '*':
return l * r
case '/':
return l / r
case '+':
return l + r
case '-':
return l - r
}
}
}
}
/**
* This is the TreeBuilder class.
* You can treat it as the driver code that takes the postinfix input
* and returns the expression tree represnting it as a Node.
*/
class TreeBuilder {
/**
* @param {string[]} s
* @return {Node}
*/
buildTree(postfix) {
const stack = []
const reg = /\d/
for (const s of postfix) {
if (reg.test(s)) {
stack.push(new TreeNode(+s))
} else {
const a = stack.pop()
const b = stack.pop()
stack.push(new TreeNode(s, b, a))
}
}
return stack[0]
}
}
/**
* Your TreeBuilder object will be instantiated and called as such:
* var obj = new TreeBuilder();
* var expTree = obj.buildTree(postfix);
* var ans = expTree.evaluate();
*/
import abc
from abc import ABC, abstractmethod
"""
This is the interface for the expression tree Node.
You should not remove it, and you can define some classes to implement it.
"""
class Node():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def evaluate(self) -> int:
if self.val.isdigit():
return int(self.val)
if self.val == '+':
return self.left.evaluate() + self.right.evaluate()
if self.val == '-':
return self.left.evaluate() - self.right.evaluate()
if self.val == '*':
return self.left.evaluate() * self.right.evaluate()
if self.val == '/':
return self.left.evaluate() // self.right.evaluate()
"""
This is the TreeBuilder class.
You can treat it as the driver code that takes the postinfix input
and returns the expression tree represnting it as a Node.
"""
class TreeBuilder(object):
def buildTree(self, postfix: List[str]) -> 'Node':
if not postfix: return None
node = Node(postfix.pop())
if node.val.isdigit():
return node
node.right = self.buildTree(postfix)
node.left = self.buildTree(postfix)
return node
"""
Your TreeBuilder object will be instantiated and called as such:
obj = TreeBuilder();
expTree = obj.buildTree(postfix);
ans = expTree.evaluate();
"""
/**
* This is the interface for the expression tree Node.
* You should not remove it, and you can define some classes to implement it.
*/
class Node {
public:
Node(const string& val) : val(val), left(nullptr), right(nullptr) {}
virtual ~Node () {};
virtual int evaluate() const
{
if (val == "+")
{
return left->evaluate() + right->evaluate();
}
else if (val == "-")
{
return left->evaluate() - right->evaluate();
}
else if (val == "*")
{
return left->evaluate() * right->evaluate();
}
else if (val == "/")
{
return left->evaluate() / right->evaluate();
}
else
{
return stoi(val);
}
}
protected:
// define your fields here
string val;
Node* left;
Node* right;
friend class TreeBuilder;
};
/**
* This is the TreeBuilder class.
* You can treat it as the driver code that takes the postinfix input
* and returns the expression tree represnting it as a Node.
*/
class TreeBuilder {
private:
stack<Node*> s;
public:
Node* buildTree(vector<string>& postfix) {
for (const string& str : postfix)
{
Node* n = new Node(str);
if (str == "+" || str == "-" || str == "*" || str == "/")
{
n->right = s.top();
s.pop();
n->left = s.top();
s.pop();
}
s.push(n);
}
return s.top();
}
};
/**
* Your TreeBuilder object will be instantiated and called as such:
* TreeBuilder* obj = new TreeBuilder();
* Node* expTree = obj->buildTree(postfix);
* int ans = expTree->evaluate();
*/
/**
* This is the interface for the expression tree Node.
* You should not remove it, and you can define some classes to implement it.
*/
abstract class Node {
public abstract int evaluate();
// define your fields here
};
/**
* This is the TreeBuilder class.
* You can treat it as the driver code that takes the postinfix input
* and returns the expression tree represnting it as a Node.
*/
class TreeBuilder {
Node buildTree(String[] postfix) {
Stack<BiOpNode> stack = new Stack<>();
for (String s : postfix) {
BiOpNode node = new BiOpNode(s);
if ("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s)) {
node.right = stack.pop();
node.left = stack.pop();
}
stack.push(node);
}
return stack.pop();
}
class BiOpNode extends Node {
String val;
BiOpNode left;
BiOpNode right;
BiOpNode(String val) {
this.val = val;
}
@Override
public int evaluate() {
switch (val) {
case "+":
return left.evaluate() + right.evaluate();
case "-":
return left.evaluate() - right.evaluate();
case"*":
return left.evaluate() * right.evaluate();
case"/":
return left.evaluate() / right.evaluate();
default:
return Integer.valueOf(val);
}
}
}
};
/**
* Your TreeBuilder object will be instantiated and called as such:
* TreeBuilder obj = new TreeBuilder();
* Node expTree = obj.buildTree(postfix);
* int ans = expTree.evaluate();
*/
