p*******m
发帖数: 47 | 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(')');
}
}
========================================= | s********0
发帖数: 34 | 2 传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); | p*******m
发帖数: 47 | 3 对的，多谢。
本来我想在Node中增加个parent, 但是你的方法很好，把current node作为parent传给
child | z****h
发帖数: 164 | 4 zan
【在 s********0 的大作中提到】
: 传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);
| w****x
发帖数: 2483 | | y****n
发帖数: 743 | 6 1. 对比运算符节点与其父节点的运算优先级。
2. 如果某运算符节点是右节点，同时其父节点是"-"或“/”，注意反转效果。
比如: a + b - (c + d) 或 a + b / (c / d)，此时括号不可收略 | f**********2
发帖数: 2401 | 7 第2点很好，没注意到
【在 y****n 的大作中提到】
: 1. 对比运算符节点与其父节点的运算优先级。
: 2. 如果某运算符节点是右节点，同时其父节点是"-"或“/”，注意反转效果。
: 比如: a + b - (c + d) 或 a + b / (c / d)，此时括号不可收略
| b******u
发帖数: 81 | 8 谢谢楼上各位的讨论和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}
}; | p*******m
发帖数: 47 | 9 电面, 大概给了20分钟。当时他给的例子很简单，只是要我不要冗余括号。
【在 w****x 的大作中提到】
: MS电面还问技术题?????
|
|
