a********e
发帖数: 53 | 1 Write a function that calculates input strings with operators +,-,*,/ eg. "5
+5*6" should output 35"。
这题好像不是leetcode上的。有什么好一点的思路吗？
我自己想到的就是首先找到* 或者/，然后计算这部分的结果，再把之前的加减运算完
成。这样scan完整个string |
R******9
发帖数: 267 | 2 http://en.wikipedia.org/wiki/Shunting-yard_algorithm
然后用reverse polish
"5
【在 a********e 的大作中提到】
: Write a function that calculates input strings with operators +,-,*,/ eg. "5
: +5*6" should output 35"。
: 这题好像不是leetcode上的。有什么好一点的思路吗？
: 我自己想到的就是首先找到* 或者/，然后计算这部分的结果，再把之前的加减运算完
: 成。这样scan完整个string
|
q****m
发帖数: 177 | 3 不需要reverse Polish,直接recursive
"5
【在 a********e 的大作中提到】
: Write a function that calculates input strings with operators +,-,*,/ eg. "5
: +5*6" should output 35"。
: 这题好像不是leetcode上的。有什么好一点的思路吗？
: 我自己想到的就是首先找到* 或者/，然后计算这部分的结果，再把之前的加减运算完
: 成。这样scan完整个string
|
N******t
发帖数: 43 | 4 我当时在facebook onsite的时候也被问到这道题。给一个string，比如“5
+5*6”，怎么做运算？
我想了好久，怎么想都绕到reverse polish上。最后面试官给个提示，假设给你split
函数，实现这个。
才知道原来可以先按“+” split，得到[5] [5*6]。对第二项用"*" split。得到[5][6
]，相乘得到30，再和前面的5加起来。 |
l***i
发帖数: 1309 | 5 use two stack, one for operands and one for operator.
when you have a new operand, push into stack.
when you have a new operator, pop operator and operands already in stack,
eval, and push result into operand stack. Keep pop and eval until the
operator at top of stack is of lower precedence. In the end, pop and eval
until stack is empty. The result of expr is in operand stack |
m******e
发帖数: 82 | 6 #include
using namespace std;
int GetSingleOperand(char* &expr) {
int num = 0;
while (*expr >= '0' && *expr <= '9') {
num = 10 * num + *expr - '0';
expr++;
}
return num;
}
int GetOperand(char* &expr) {
int num = GetSingleOperand(expr);
while (*expr != '\0') {
if (*expr == '*') {
expr++;
num *= GetSingleOperand(expr);
} else if (*expr == '/') {
expr++;
num /= GetSingleOperand(expr);
} else {
break;
}
}
return num;
}
int Calculate(char expr[]) {
if (*expr == '\0') // empty
return 0;
int result = GetOperand(expr);
while (*expr != '\0') {
if (*expr == '+') {
expr++;
result += GetOperand(expr);
} else if (*expr == '-') {
expr++;
result -= GetOperand(expr);
}
}
return result;
}
int main()
{
char expr[] = "3*4+2*3-10/2";
cout << Calculate(expr) << endl;
return 0;
} |
f******n
发帖数: 279 | |
i*******t
发帖数: 79 | 8 编译原理的例题
"5
【在 a********e 的大作中提到】
: Write a function that calculates input strings with operators +,-,*,/ eg. "5
: +5*6" should output 35"。
: 这题好像不是leetcode上的。有什么好一点的思路吗？
: 我自己想到的就是首先找到* 或者/，然后计算这部分的结果，再把之前的加减运算完
: 成。这样scan完整个string
|
a**********s
发帖数: 588 | 9 对啊，这个是最基本的题了，看到下一个op优先级不比当前的优先级高就计算完当前的
op，然后push next op, next operand
【在 i*******t 的大作中提到】
: 编译原理的例题
:
: "5
|
