pets版争论指南，今天发贴前必看 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>pets - 心有所宠

pets版争论指南，今天发贴前必看

pets版争论指南，今天发贴前必看# pets - 心有所宠

N*o2011-11-16 08:11

1 楼

其他人却付伪币呢

S*I2011-11-16 08:11

2 楼

☆─────────────────────────────────────☆
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分钟。当时他给的例子很简单，只是要我不要冗余括号。

G*Y2011-11-16 08:11

3 楼

【以下文字转载自 Seattle 讨论区】
发信人: GGYY (唧唧歪歪), 信区: Seattle
标题: 也上薰衣草
发信站: BBS 未名空间站 (Tue Jul 20 03:34:31 2010, 美东)
如题

y*u2011-11-16 08:11

4 楼

[updated by PALA]: 所有版务投诉相关帖，支持的，反对的，都合集了放在精华区目
录下。
http://74.53.4.74/bbsdoc3/thinking.faq/pets/board_affair/8/D132
再想讨论版务的，请去投诉版吧。现在还有开新贴讨论这些的，一律直接删。
============================================================================
发现我此刻还是版务，那就得做点事情，给大家个指南吧。
事情原始贴：http://www.mitbbs.com/article_t2/pets/32282235.html
事情发展贴：考古请站内搜索30天内的＂合集＂，或者精华区->宠物宠务->争议话题
支持弹劾柴鱼者：请去complain版面回应
http://www.mitbbs.com/article_t/Complain/31280179.html
反对弹劾柴鱼者：请去complain版面回应
http://www.mitbbs.com/article_t/Complain/31280179.html
支持弹劾pala者：请去complain版面回应
http://www.mitbbs.com/article_t/Complain/31280089.html
反对弹劾pala者：请去complain版面回应
http://www.mitbbs.com/article_t/Complain/31280089.html
关心pala私生活者：请申请开＂我们都爱pala＂俱乐部
厌恶pala说话做事风格者：请申请开＂我们都恨pala＂俱乐部
喜欢pets者，请继续发照片，和其他任何和pets有关的贴。我不锁贴，免的被戴上控
制言论自由的帽子，但希望大家自觉不要违反版规，不要让讨论个人事情占据整个版面
，还有很多新ID旧ID要问问题，求祝福和发PP。
谢谢！