h*****g
发帖数: 312 | 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 |
i*****e
发帖数: 63 | 2 convert it to postfix(or prefix) first and then convert it back to infix?? |
y****n
发帖数: 743 | 3 假设运算符只包括：+,-,*,/
对运算符给定优先级： (+,-) < (*, /)
对输入表达式进行扫描：对比括号前和后的运算符优先级和括号内的最低优先级来判断
括号是否可以消除。
注意，有个例外，就是括号前的/和-会对括号内容有反转作用。
比如：a - (b - c) 和 x / (y * z) |
t****t
发帖数: 6806 | 4 加法和乘法有结合律吗? (即应用结合律是否影响计算结果)
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
|
h*****g
发帖数: 312 | 5 code 得咋写？
【在 i*****e 的大作中提到】
: convert it to postfix(or prefix) first and then convert it back to infix??
|
y****n
发帖数: 743 | 6 扫描式，空间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);
}
} |
