又扣一枪 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PhotoGear - 摄影器材

又扣一枪

又扣一枪# PhotoGear - 摄影器材

h*g2010-04-04 07:04

1 楼

Given an expression remove the unnecessary brackets in it with out creating
an ambiguity in its execution.
input output
ex1: (a+(b)+c) a+b+c
ex2: (a*b)+c a*b+c

p*e2010-04-04 07:04

2 楼

http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=270558229298

i*e2010-04-04 07:04

3 楼

convert it to postfix(or prefix) first and then convert it back to infix??

T*t2010-04-04 07:04

4 楼

有空给我扣几枪

【在 p********e 的大作中提到】

: http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=270558229298

y*n2010-04-04 07:04

5 楼

假设运算符只包括：+,-,*,/
对运算符给定优先级： (+,-) < (*, /)
对输入表达式进行扫描：对比括号前和后的运算符优先级和括号内的最低优先级来判断
括号是否可以消除。
注意，有个例外，就是括号前的/和-会对括号内容有反转作用。
比如：a - (b - c) 和 x / (y * z)

S*t2010-04-04 07:04

6 楼

cong

【在 p********e 的大作中提到】

: http://cgi.ebay.com/ws/eBayISAPI.dll?ViewItem&item=270558229298

t*t2010-04-04 07:04

7 楼

加法和乘法有结合律吗? (即应用结合律是否影响计算结果)

creating

【在 h*****g 的大作中提到】

: Given an expression remove the unnecessary brackets in it with out creating
: an ambiguity in its execution.
: input output
: ex1: (a+(b)+c) a+b+c
: ex2: (a*b)+c a*b+c

j*x2010-04-04 07:04

8 楼

价格很好呀，原价出我吧。。。

h*g2010-04-04 07:04

9 楼

code 得咋写？

【在 i*****e 的大作中提到】

: convert it to postfix(or prefix) first and then convert it back to infix??

y*n2010-04-04 07:04

10 楼

扫描式，空间O(n)，时间O(n)，一遍扫描。
public class BracketInfo
{
public char OperatorBefore = '\0'; // Low-Pri
public char OperatorInner = '$'; // Hi-Pri
public char OperatorAfter = '\0'; // Low-Pri
public int BracketStart = -1;
public int BracketEnd = -1;
}
public class BracketChecker
{
private Dictionary operatorPriority = null;
public Dictionary OperatorPriority
{
get
{
if (this.operatorPriority == null)
{
// Init operator priorites
this.operatorPriority = new Dictionary();
this.operatorPriority['$'] = 8;
this.operatorPriority['/'] = 4;
this.operatorPriority['*'] = 4;
this.operatorPriority['-'] = 2;
this.operatorPriority['+'] = 2;
this.operatorPriority['\0'] = 0;
}
return this.operatorPriority;
}
}
public bool IsRemovable(BracketInfo bracket)
{
int beforePriority = this.OperatorPriority[bracket.
OperatorBefore];
if ((bracket.OperatorBefore == '/') || (bracket.OperatorBefore =
= '-'))
beforePriority++;
// Compare inner operator with before and end operators
if ((this.OperatorPriority[bracket.OperatorInner] >= this.
OperatorPriority[bracket.OperatorAfter])
&& (this.OperatorPriority[bracket.OperatorInner] >=
beforePriority))
return true;
else
return false;
}
public string RemoveBrackets(string expression)
{
char[] buffer = expression.ToCharArray();
List brackets = new List();
int bracketDepth = 0;
char lastOperator = '\0';
for (int i = 0; i < buffer.Length; i++)
{
char ch = buffer[i];
switch (ch)
{
case '(':
brackets.Add(new BracketInfo());
bracketDepth++;
brackets[bracketDepth - 1].OperatorBefore =
lastOperator;
brackets[bracketDepth - 1].BracketStart = i;
lastOperator = '\0';
break;
case ')':
brackets[bracketDepth - 1].BracketEnd = i;
bracketDepth--;
break;
case '+':
case '-':
case '*':
case '/':
lastOperator = ch;
// Update inner operator if in a bracket
if ((bracketDepth > 0)
&& (this.OperatorPriority[brackets[bracketDepth
- 1].OperatorInner] > this.OperatorPriority[ch]))
brackets[bracketDepth - 1].OperatorInner = ch;
if (bracketDepth < brackets.Count)
{
// Check finished bracket
BracketInfo bracket = brackets[bracketDepth];
bracket.OperatorAfter = ch;
if (this.IsRemovable(bracket))
{
buffer[bracket.BracketStart] = ' ';
buffer[bracket.BracketEnd] = ' ';
brackets.RemoveAt(bracketDepth);
}
}
break;
}
}
if (bracketDepth < brackets.Count)
{
BracketInfo bracket = brackets[bracketDepth];
if (this.IsRemovable(bracket))
{
buffer[bracket.BracketStart] = ' ';
buffer[bracket.BracketEnd] = ' ';
brackets.RemoveAt(bracketDepth);
}
}
return new String(buffer);
}
}