S**I
发帖数: 15689 | 1 ☆─────────────────────────────────────☆
princekim (Prince Kim) 于 (Wed Apr 11 09:32:26 2012, 美东) 提到:
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(')');
}
}
=========================================
☆─────────────────────────────────────☆
sandra1210 (sandra1210) 于 (Wed Apr 11 10:58:35 2012, 美东) 提到:
传parent的指针下去，如果parent的运算符优先级高 则加（）否则直接返回结果；
int get_priority(node *root){
if(!root) return 0;
if(root->operator == ‘+’ || root->operator == ‘-’) return 1;
return 2;
}
string get_expression(node *root, node *parent){
if(!root->left && !root->right) return root->operand;
string ans;
string left = get_expression(root->left, root);
string right = get_expression(root->right, root);
if(get_priority(parent) > get_priority(root)){
ans += “(“ + left + root->operator+ right + “)”;
}
else ans = left + root->operator + right;
return ans;
}
get_expression(root, NULL);
☆─────────────────────────────────────☆
princekim (Prince Kim) 于 (Wed Apr 11 12:04:23 2012, 美东) 提到:
对的，多谢。
本来我想在Node中增加个parent, 但是你的方法很好，把current node作为parent传给
child
☆─────────────────────────────────────☆
zhangh (zhuangzhuang) 于 (Wed Apr 11 13:25:27 2012, 美东) 提到:
zan
☆─────────────────────────────────────☆
wwwyhx (wwwyhx) 于 (Wed Apr 11 13:48:55 2012, 美东) 提到:
MS电面还问技术题?????
☆─────────────────────────────────────☆
yishan (易山风雨易江秋) 于 (Wed Apr 11 14:29:11 2012, 美东) 提到:
1. 对比运算符节点与其父节点的运算优先级。
2. 如果某运算符节点是右节点，同时其父节点是"-"或“/”，注意反转效果。
比如: a + b - (c + d) 或 a + b / (c / d)，此时括号不可收略
☆─────────────────────────────────────☆
flyinocean12 (生无所求) 于 (Wed Apr 11 18:13:11 2012, 美东) 提到:
第2点很好，没注意到
☆─────────────────────────────────────☆
bajiezhu (zhu tou) 于 (Thu Apr 12 05:38:42 2012, 美东) 提到:
谢谢楼上各位的讨论和CODE。很有启发性。
public static string GetExpression(Node node, string parentOp, bool?
isLeft=null)
{
if (node.Operator == null) return node.Operand.ToString();
bool addParenthesis = ToAdd2(node, parentOp, isLeft);
return ((addParenthesis) ? "(" : "") +
GetExpression(node.Left, node.Operator, true) +
node.Operator +
GetExpression(node.Right, node.Operator, false) +
( (addParenthesis) ? ")" : "");
}
private static bool ToAdd2(Node opNode, string parentOp, bool?
isLeft)
{
if (isLeft == null) return false;
int[,] array = isLeft.Value? LeftMatrix : RightMatrix;
return array[GetOp(parentOp), GetOp(opNode.Operator)] == 1;
}
private static int GetOp(string op)
{
switch (op)
{
case ("+"): return 0;
case ("-"): return 1;
case ("*"): return 2;
case ("/"): return 3;
default: return 0;
}
}
private static int[,] LeftMatrix =
{
{0, 0, 0, 0},
{0, 0, 0, 0},
{1, 1, 0, 0},
{1, 1, 0, 0}
};
private static int[,] RightMatrix =
{
{0, 0, 0, 0},
{1, 1, 0, 0},
{1, 1, 0, 0},
{1, 1, 1, 1}
};
☆─────────────────────────────────────☆
princekim (Prince Kim) 于 (Thu Apr 12 15:18:51 2012, 美东) 提到:
电面, 大概给了20分钟。当时他给的例子很简单，只是要我不要冗余括号。 |
|
