ajwook 独立后发nature了# Biology - 生物学
p*m
1 楼
BT树结构, 中间节点是算数运算符(只有+ - * / 4种操作), 叶节点是数字, 要求给出
算数表达式 (要求没有冗余括号)
比如
*
/ \
+ *
/ \ / \
1 2 4 5
表达式 = (1 + 2) * 4 * 5, 不能是 (1+2)*(4*5)
+
/ \
* +
/ \ / \
1 2 4 5
表达式 = 1 * 2 + 4 + 5, 不能是 1 * 2 + (4 + 5)
总之, 这题的难点是 算数表达式不能有冗余括号
我当时的思路: in-order 递归遍历, 遇到 + - 给出左右括号 (但这样就有冗余括号).
面试官指出后, 我说我可以再扫描遍得到的表达式，去除冗余括号 (这也是我情急下
蒙的).
他说不行, 只能在遍历BT时一次完成. 他提示考虑运算符的优先级, 但后来时间到了,
也就草草收场
真心请教思路, 多谢
=========================================
class Node{
char value;
Node left, right;
}
class ArithExp{
ArrayList expression = new ArrayList(); //
global variable
/*
* recursion, in-order walk
*/
public static void in_order_walk(Node root){
if(root == null)
return;
// store result at expression
// for arithmetical operations, only + - need (), * / don't need ()
if(root.value == '+' || root.value == '-')
expression.add('(');
in_order_walk(root.left);
expression.add(root.value);
in_order_walk(root.right);
if(root.value == '+' || root.value == '-')
expression.add(')');
}
}
=========================================
算数表达式 (要求没有冗余括号)
比如
*
/ \
+ *
/ \ / \
1 2 4 5
表达式 = (1 + 2) * 4 * 5, 不能是 (1+2)*(4*5)
+
/ \
* +
/ \ / \
1 2 4 5
表达式 = 1 * 2 + 4 + 5, 不能是 1 * 2 + (4 + 5)
总之, 这题的难点是 算数表达式不能有冗余括号
我当时的思路: in-order 递归遍历, 遇到 + - 给出左右括号 (但这样就有冗余括号).
面试官指出后, 我说我可以再扫描遍得到的表达式，去除冗余括号 (这也是我情急下
蒙的).
他说不行, 只能在遍历BT时一次完成. 他提示考虑运算符的优先级, 但后来时间到了,
也就草草收场
真心请教思路, 多谢
=========================================
class Node{
char value;
Node left, right;
}
class ArithExp{
ArrayList
global variable
/*
* recursion, in-order walk
*/
public static void in_order_walk(Node root){
if(root == null)
return;
// store result at expression
// for arithmetical operations, only + - need (), * / don't need ()
if(root.value == '+' || root.value == '-')
expression.add('(');
in_order_walk(root.left);
expression.add(root.value);
in_order_walk(root.right);
if(root.value == '+' || root.value == '-')
expression.add(')');
}
}
=========================================
