f*******7
发帖数: 943 | 1 题目一出，我就傻眼了，就知道完蛋了。。。
这题目正好是隔壁BB Onsite面经第二题
给一个表达式，计算返回值，不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天，问对方，对吗？ 多方说，你说呢。。。
祝大家好运吧，哪个大牛给个链接 |
p*****2
发帖数: 21240 | 2 看了一下。这题你怎么做的？
感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。 |
a***o
发帖数: 1182 | 3 stack就行了,或者搞个temp variable
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
|
h*******0
发帖数: 270 | 4 2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
recursive。 我说recursive不好，被华丽丽的鄙视了。。。
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
|
p*****2
发帖数: 21240 | 5
stack更简单吗？
【在 a***o 的大作中提到】
: stack就行了,或者搞个temp variable
|
p*****2
发帖数: 21240 | 6
recursive怎么搞呀？
【在 h*******0 的大作中提到】
: 2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
: recursive。 我说recursive不好，被华丽丽的鄙视了。。。
|
f*******7
发帖数: 943 | 7 二爷这题我没见过，硬着头皮写recursive，思路都不对，今天就问了这一题。。。
有相关讲解的链接吗？
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
|
h*******0
发帖数: 270 | 8 我当时也没想出来。 然后我和他说，我这个方法比recursive好。。 我说recursive可
能会out of memory。 人家根本不同意我的说法。
【在 p*****2 的大作中提到】
:
: recursive怎么搞呀？
|
h*******0
发帖数: 270 | 9 我觉得如果见到没见过的题就要赶紧研究。。 弄不好就是你下一道题。。 这题其实挺
不好写的
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
|
p*****2
发帖数: 21240 | 10
我大概的想法
1000-5*6/3*2+1
用个双向链表
1000 - 5 * 6 / 3 * 2 + 1
第一遍算乘除， 比如 看到第一个 ＊ 就把prev * next 然后把5*6拿掉，把结果30放
进去，就成了
1000 - 30 / 3 * 2 + 1
第二遍算加减就从头算到尾就可以了
想想有没有什么更简单的办法。
【在 f*******7 的大作中提到】
: 二爷这题我没见过，硬着头皮写recursive，思路都不对，今天就问了这一题。。。
: 有相关讲解的链接吗？
|
|
|
a***o
发帖数: 1182 | 11 搞俩variable就行了,一个存之前的数,
一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数
【在 p*****2 的大作中提到】
:
: 我大概的想法
: 1000-5*6/3*2+1
: 用个双向链表
: 1000 - 5 * 6 / 3 * 2 + 1
: 第一遍算乘除， 比如 看到第一个 ＊ 就把prev * next 然后把5*6拿掉，把结果30放
: 进去，就成了
: 1000 - 30 / 3 * 2 + 1
: 第二遍算加减就从头算到尾就可以了
: 想想有没有什么更简单的办法。
|
p****e
发帖数: 3548 | 12 搞了个复杂的。。
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
bool OpHigherOrder(char c1, char c2)
{
if(c1 != '(' && c2 == ')')
return true;
else if(c1 == '(')
return false;
else if((c1 == '*' || c1 == '/'))
return true;
else if((c1 == '+' || c1 == '-') && (c2 == '+' || c2 == '-'))
return true;
else
return false;
}
double CalOp(double e1, char op, double e2)
{
switch(op)
{
case '+':
return e1 + e2;
case '-':
return e1 - e2;
case '*':
return e1 * e2;
case '/':
return e1 / e2;
}
}
double CalExpression(string a)
{
stack num;
stack op;
int numpos = 0;
for(int i = 0; i < a.length(); i++)
{
if(a[i] == ' ')
{
a.erase(i, 1);
i--;
continue;
}
if((a[i]>='0' && a[i]<='9') || a[i] == '.')
{
continue;
}
if(a[i] == '(')
{
op.push('(');
numpos = i + 1;
continue;
}
if(numpos < i)
{
num.push(atof(a.substr(numpos, i - numpos).c_str()));
}
while(op.size() > 0 && num.size()>1)
{
if(OpHigherOrder(op.top(), a[i]))
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
else
{
break;
}
}
if(a[i] == ')')
{
op.pop();
}
else
op.push(a[i]);
numpos = i + 1;
}
if(numpos < a.length())
num.push(atof(a.substr(numpos).c_str()));
while(op.size() > 0 && num.size()>1)
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
return num.top();
}
int main() {
// Start typing your code here...
string s("12+5*62/2-3*(5+3*(5+6))");
cout << CalExpression(s) << endl;
return 0;
} |
p*****2
发帖数: 21240 | 13 1000-5*6/3*2+1
recursion的话
1000 － 然后往后找到 ＋， － 或者end
变成
1000- f(5*6/3*2) + 1
主要是纪录＋－的位置。比如上边的例子，4 13
然后分段算 f(0,3) - f(5, 12) + f(14) |
h*******8
发帖数: 29 | |
p*****2
发帖数: 21240 | 15
应该可以。就是写起来不知道是不是容易bug free。你可以写写看看。
【在 a***o 的大作中提到】
: 搞俩variable就行了,一个存之前的数,
: 一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数
|
o***d
发帖数: 313 | 16 我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
敏的书
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
|
o***d
发帖数: 313 | 17 另外,这个我在careercup上见过google也考过似乎
【在 o***d 的大作中提到】
: 我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
: 敏的书
|
b*****u
发帖数: 648 | 18 试着写了一个递归的
思路： 每个recursion的开始有一个factor，一个当前operand和一个之前乘/除号
首先把operand = operand 乘除 factor
然后，如果下一符号是加减，则返回 operand 加减下一recursion（factor=1， 乘）
如果下一符号是乘除，则返回下一recursion (factor=当前operand, 下一符号）
(on a second thought, 这个其实也就是实现了一个stack的功能，递归即stack)
#include "stdafx.h"
#include
#include
#include
using namespace std;
int stringCalculator(string input, int factor, char sign)
{
int len = input.length();
if (len == 0) return 0;
int i = 0;
while (i< len && input[i]>='0' && input[i]<='9')
{
++i;
}
int rightEnd = min (len, i);
int operand = atoi(input.substr(0,rightEnd).c_str());
if (sign == '*')
operand *= factor;
else
operand /= factor;
if (i == len)
return operand;
else
{
switch (input[i])
{
case '+':
return operand+stringCalculator(input.substr(i+1), 1, '*');
case '-':
return operand-stringCalculator(input.substr(i+1), 1, '*');
default:
return stringCalculator(input.substr(i+1), operand, input[i]);
break;
}
}
}
int calculator (string input)
{
return stringCalculator(input,1,'*');
}
int _tmain(int argc, _TCHAR* argv[])
{
string test = "1+2*3";
cout << calculator (test);
cin.get();
return 0;
} |
m*****1
发帖数: 147 | 19 电面考这个，要求有点高啊，写计算器是以前学做编译原理搞语法和词法分析的小
project哎 |
w****x
发帖数: 2483 | 20 int mul(const char*& p);
int num(const char*& p);
int Add(const char*& p)
{
int res = mul(p);
while (*p == '+' || *p == '-')
{
if (*p == '+')
res += mul(++p);
else
res -= mul(++p);
}
return res;
}
int mul(const char*& p)
{
int res = num(p);
while (*p == '*' || *p == '/')
{
if (*p == '*')
res *= num(++p);
else
res /= num(++p);
}
return res;
}
int num(const char*& p)
{
bool bNeg = false;
if (*p == '-')
{
bNeg = true;
p++;
}
int res = 0;
while (*p >= '0' && *p <= '9')
res = res*10 + *p++ - '0';
return bNeg ? -res : res;
}
递归下降
Add = mul | (+- mul)*
mul = num | (+- num)*
num = (+-)[0-9]* |
|
|
j*****y
发帖数: 1071 | 21 int value(int a, int b, char c)
{
if(c == '+') return a + b;
if(c == '-') return a - b;
if(c == '*') return a * b;
if(c == '/') return a / b;
}
int expression(vector s)
{
if(s.size() == 0)
{
return 0;
}
stack operand;
stack operator;
operand.push(atoi(s.c_str()));
for(int i = 0; i < input.size(); ++i)
{
if(isnumber(s[i][0]))
{
operand.push(atoi(s[i].c_str()));
}
else
{ char c = s[i][0];
if(c == '*' || c == '/')
{
int a = atoi(s[++i].c_str());
a = value(operand.top(), a, c);
operand.pop();
operand.push(a);
}
else
{
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
operand.pop();
operand.push(value(a, b, operator.top()));
operator.pop();
}
else
{
operator.push(c);
}
}
}
}
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
return value(a, b, operator.top());
}
else
{
return operand.top();
}
}
感觉不用 stack也可以， 因为 stack里面只有一个或者两个 item
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
|
p*****2
发帖数: 21240 | 22 def cal(str:String):Int={
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(i<-0 until operators.length) operators(i) match{
case '+' => result+=numbers(i+1)
case '-' => result-=numbers(i+1)
case '*' => result*=numbers(i+1)
case '/' => result/=numbers(i+1)
}
result
}
def solve(str:String):Int={
val plusminus= -1 +: (for(i<-0 until str.length if str(i)=='+' ||
str(i)=='-') yield i)
var sb=new StringBuilder()
for(i<-1 until plusminus.length){
sb.append(cal(str.slice(plusminus(i-1)+1,plusminus(i))))
sb.append(str(plusminus(i)))
}
sb.append(cal(str.slice(plusminus.last+1, str.length)))
cal(sb.toString)
} |
h*******0
发帖数: 270 | 23 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
【在 w****x 的大作中提到】
: int mul(const char*& p);
: int num(const char*& p);
: int Add(const char*& p)
: {
: int res = mul(p);
: while (*p == '+' || *p == '-')
: {
: if (*p == '+')
: res += mul(++p);
: else
|
q********s
发帖数: 1032 | 24 这个不是逆波兰吗？
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
|
a***o
发帖数: 1182 | 25 写的漂亮,可能C比较简洁
【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
|
e****e
发帖数: 418 | 26 凑个热闹!
public int calculate( String[] in, int sIdx ) {
if ( sIdx == in.length - 1)
return toInt( in[sIdx] );
int addOrMinus = getAddOrMinusSign( in[sIdx + 1] );
if ( addOrMinus != 0 ) {
if ( sIdx + 2 == in.length - 1 || getAddOrMinusSign( in[sIdx + 3] ) !=
0 ) {
in[sIdx+2] = toStr( toInt( in[sIdx] ) + addOrMinus*toInt( in[sIdx+
2] ) );
return calculate( in, sIdx + 2 );
} else {
calMulOrDivAndSetBack( in, sIdx+2 );
in[sIdx+3] = in[sIdx+1];
in[sIdx+2] = in[sIdx];
return calculate( in, sIdx + 2 );
}
}
calMulOrDivAndSetBack( in, sIdx );
return calculate( in, sIdx + 2 );
}
private int getAddOrMinusSign( String s ){
if ( "+".equals( s ) )
return 1;
else if ( "-".equals( s ) )
return -1;
return 0;
}
private void calMulOrDivAndSetBack( String[] in, int idx ) {
if ( "*".equals( in[idx + 1] ) )
in[idx+2] = toStr( toInt( in[idx] ) * toInt( in[idx+2] ) );
else
in[idx+2] = toStr( toInt( in[idx] ) / toInt( in[idx+2] ) );
}
private int toInt( String s ){
return Integer.parseInt( s );
}
private String toStr( Integer i ) {
return Integer.toString( i );
} |
w****x
发帖数: 2483 | 27
可能因为我比较帅吧
【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
|
l*****a
发帖数: 14598 | 28 看linkedin不像啊
【在 w****x 的大作中提到】
:
: 可能因为我比较帅吧
|
w****x
发帖数: 2483 | 29
等等，我马上换成刘德华的
【在 l*****a 的大作中提到】
: 看linkedin不像啊
|
s*********s
发帖数: 140 | 30 贴个java recursive的吧。
float compute(String exp) {
if(exp == null || exp.length() == 0) return 0;
int plusPos = exp.indexOf('+');
int minusPos = exp.indexOf('-');
if(plusPos < 0 && minusPos < 0) return convert(exp);
if(plusPos < 0 || (minusPos > 0 && minusPos < plusPos))
return convert(exp.substring(0, minusPos)) - compute(exp.
substring(minusPos+1));
if(minusPos < 0 || (plusPos > 0 && plusPos < minusPos))
return convert(exp.substring(0, plusPos)) + compute(exp.
substring(plusPos+1));
return 0;
}
float convert(String exp){
float res = 1;
float curr = 0;
boolean isProduct = true;
for(int i = 0; i < exp.length(); i++){
if(exp.charAt(i) == '*' || exp.charAt(i) == '/'){
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is
0");
else res = res/curr;
}
curr = 0;
isProduct = (exp.charAt(i) == '*');
} else {
curr = curr * 10 + (float)(exp.charAt(i) - '0');
}
}
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is 0");
else res = res/curr;
}
return res;
} |
|
|
x*******6
发帖数: 262 | 31 先把表达式转换成operand和operator的string[],再转换成postfix notation，最后用
一个stack来帮助计算 |
p*****2
发帖数: 21240 | 32
这个看起来不错。
【在 w****x 的大作中提到】
: int mul(const char*& p);
: int num(const char*& p);
: int Add(const char*& p)
: {
: int res = mul(p);
: while (*p == '+' || *p == '-')
: {
: if (*p == '+')
: res += mul(++p);
: else
|
s****0
发帖数: 117 | |
l*********8
发帖数: 4642 | 34 double readNumber(const char * &str) {
double num;
sscanf(str, "%lf", &num);
for (++str; isdigit(*str) || *str == '.'; ++str)
;
return num;
}
double calculate(const char * str) {
if (*str == '\0') return 0.0;
double result = 1.0;
char op = '*';
while (op == '*' || op == '/') {
if (op == '*')
result *= readNumber(str);
else
result /= readNumber(str);
op = *str++;
}
return result + calculate(--str);
} |
l*********8
发帖数: 4642 | 35 测试案例：
-3-4.3+5.05*2/4-4.10/5+3 = -2.595
【在 l*********8 的大作中提到】
: double readNumber(const char * &str) {
: double num;
: sscanf(str, "%lf", &num);
: for (++str; isdigit(*str) || *str == '.'; ++str)
: ;
: return num;
: }
: double calculate(const char * str) {
: if (*str == '\0') return 0.0;
: double result = 1.0;
|
l*******b
发帖数: 2586 | 36 学习了...发愁那个减号怎么处理呢...原来是sscanf...哈哈
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
|
s****0
发帖数: 117 | 37 package myutil;
import java.util.Scanner;
import java.util.Stack;
public class ParseExp {
Stack oprand = new Stack();
Stack oprator = new Stack();
static int[] code = new int[256];
static {
code['+'] = 10;
code['-'] = 11;
code['*'] = 20;
code['/'] = 21;
code['^'] = 30;
code['$'] = 0;
code['('] = 100;
code[')'] = 1;
}
public ParseExp() {
}
public Integer parse(String e) {
Scanner s = new Scanner(e + " $");
oprator.push(-1);
while (true) {
if (s.hasNextInt()) {
oprand.push(s.nextInt());
} else if (s.hasNext("[-$+*/^()]")) {
int optr = code[s.next(".").charAt(0)];
while (!oprator.isEmpty() && oprator.peek() > optr) {
int y = oprand.pop();
int x = oprand.pop();
switch (oprator.pop()) {
case 10:
oprand.push(x + y);
break;
case 11:
oprand.push(x - y);
break;
case 20:
oprand.push(x * y);
break;
case 21:
oprand.push(x * y);
break;
case 30:
oprand.push((int) Math.pow(x, y));
break;
}
}
if (optr == 0)
break;
if (optr == 100) {
oprator.push(1);
continue;
} else if (optr == 1) {
oprator.pop();
continue;
} else
oprator.push(optr);
} else {
System.out.println(s.next());
}
}
return oprand.peek();
}
public static void main(String[] args) {
ParseExp p = new ParseExp();
for (String e : new String[] { "1 + 1", "1 + 2 * 3", "1 * 2 + 3",
"1 + 2 * 3 + 4", "2 ^ 8 + 1 * 4", "1 * 4 + 2 ^ 8 - 4",
"( 2 + 3 ) * ( 4 + 6 ) ^ 2" }) {
System.out.println(e + " = " + p.parse(e));
}
}
} |
M******l
发帖数: 479 | 38 逆波兰表达式吧？用个stack就行了，两年前面试被问过，当时居然正好复习到了～～
http://baike.baidu.com/view/552648.htm
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
|
c*****a
发帖数: 808 | |
p*****2
发帖数: 21240 | 40
longway又出手了。
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
|
|
|
H****s
发帖数: 247 | 41 还是这个牛啊！
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
|
p*****2
发帖数: 21240 | 42
longway的代码向来都是最简洁的。
【在 H****s 的大作中提到】
: 还是这个牛啊！
|
e****e
发帖数: 418 | 43 写了一个infix to postfix，实现起来简单, 不知道思路还真不好想，面试的时候我肯
定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
public List toPostfix(String[] in) {
List pf = new ArrayList();
Stack stack = new Stack();
for ( String s : in ) {
int p = getPrecedence( s );
if ( p == 0 )
pf.add( s );
else if ( stack.empty() )
stack.push( s );
else {
while( !stack.isEmpty() && getPrecedence( stack.peek() ) >= p )
pf.add( stack.pop() );
stack.push( s );
}
}
while( !stack.isEmpty() )
pf.add( stack.pop() );
return pf;
}
private int getPrecedence(String s) {
switch( s ) {
case "*": return 2;
case "/": return 2;
case "+": return 1;
case "-": return 1;
default : return 0;
}
}
【在 M******l 的大作中提到】
: 逆波兰表达式吧？用个stack就行了，两年前面试被问过，当时居然正好复习到了～～
: http://baike.baidu.com/view/552648.htm
|
p*****2
发帖数: 21240 | 44
这东西没搞过。回头看看。
【在 e****e 的大作中提到】
: 写了一个infix to postfix，实现起来简单, 不知道思路还真不好想，面试的时候我肯
: 定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
: public List toPostfix(String[] in) {
: List pf = new ArrayList();
: Stack stack = new Stack();
: for ( String s : in ) {
: int p = getPrecedence( s );
: if ( p == 0 )
: pf.add( s );
: else if ( stack.empty() )
|
l*********8
发帖数: 4642 | 45 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
|
d********f
发帖数: 43471 | 46 20年前你这么回答可能还行
【在 h*******0 的大作中提到】
: 我当时也没想出来。 然后我和他说，我这个方法比recursive好。。 我说recursive可
: 能会out of memory。 人家根本不同意我的说法。
|
n***e
发帖数: 723 | 47 哈哈，这个牛！居然能这么处理。
【在 l*********8 的大作中提到】
: 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
|
I**********s
发帖数: 441 | 48 最喜欢 wwwyhx的解法: recursive descent.
我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
#include
#include // for pow()
using namespace std;
struct Node {
double val;
char op;
int op_prec; // precedence of operator
int type; // 0 - operand, 1 - operator
Node * left;
Node * right;
Node(double _val, char _op, int _type) : val(_val), op(_op),
type(_type), left(NULL), right(NULL) {}
};
class Solution {
private:
int prec_base;
const char * p0; // record start position of input string.
void err(char * msg, const char * p) {
printf("input error: %s, at input position %d\n", msg, p - p0);
printf("%s\n", p0);
for (int i = 0, len = p - p0; i < len; ++ i) putchar(' ');
printf("^\n");
exit(1);
}
void dump_node(Node * n) {
if (n->type == 0) printf(" %.1lf ", n->val);
else printf(" %c ", n->op);
}
void dump(Node * n) {
if (! n) return;
if (! n->left && ! n->right) {
dump_node(n);
return;
}
printf("(");
dump(n->left);
dump_node(n);
dump(n->right);
printf(")");
}
int prec(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
if (op == '^') return 3;
return 0;
}
int isOp(char c) {
return (c == '+' || c == '-' || c == '*' ||
c == '/' || c == '^');
}
int isDigit(char c) { return c >= '0' && c <= '9'; }
// type - desired type of new token. 0 - operand, 1 - operator.
Node * getNextToken(const char *& input, int type) {
const int prec_base_inc = 4; // 1 + max(op prec)
while (isspace(*input)) ++ input; // skips spaces.
if (! *input) return NULL; // end of input.
while (*input == '(') {
prec_base += prec_base_inc;
++ input;
}
// check if is desired type.
if (! ((type == 1 && isOp(*input) ) ||
(type == 0 && (isDigit(*input) || *input == '+' ||
*input== '-' || *input=='.'))) ) {
err("wrong type of operand/operator", input);
}
Node * n;
if (type == 1) { // operator.
n = new Node(0, *input, type);
n->op_prec = prec(n->op) + prec_base;
++ input;
}
else { // type == 0: operand.
double val;
// sscanf requires no space between sign and value.
sscanf(input, "%lf", &val);
n = new Node(val, 0, type);
if (*input == '+' || *input == '-') ++ input;
if (! (isDigit(*input) || *input == '.')) {
err("incomplete number", input);
}
bool dot_used = false; // allow only one dot.
while ( isDigit(*input) || (*input == '.' && !dot_used)) {
if (*input == '.') dot_used = true;
++ input;
}
while (*input == ')') {
prec_base -= prec_base_inc;
++ input;
}
}
return n;
}
void buildAST(const char * input, Node *& root) {
root = getNextToken(input, 0);
while (1) {
Node * opt = getNextToken(input, 1);
if (! opt) return; // end of input.
Node * opd = getNextToken(input, 0);
if (root->type == 0 || opt->op_prec <= root->op_prec) {
opt->left = root;
opt->right = opd;
root = opt;
} else {
Node * n = root;
while (1) {
if (n->right->type == 0 ||
opt->op_prec <= n->right->op_prec) {
opt->left = n->right;
opt->right = opd;
n->right = opt;
break;
} else {
n = n->right;
}
} // end of while
} // end of if
} // end of while
}
double eval(Node * t) {
if (! t) return 0;
if (t->type == 0) return t->val; // t is operand.
// t is operator.
if (t->op == '+') return eval(t->left) + eval(t->right);
if (t->op == '-') return eval(t->left) - eval(t->right);
if (t->op == '*') return eval(t->left) * eval(t->right);
if (t->op == '/') return eval(t->left) / eval(t->right);
if (t->op == '^') return pow(eval(t->left), eval(t->right));
}
public:
Solution() { prec_base = 0; }
~Solution() { /* destroy AST. */ }
double calc(const char * s) {
p0 = s; // record start pointer position.
Node * p = NULL;
buildAST(s, p);
dump(p); puts("");
return eval(p);
}
};
int main() {
const char * input = "(1 + 2)*((3-1)- 3.5) + 4^2";
Solution s;
cout << "Solution 1: " << s.calc(input) << endl;
return 0;
} |
I**********s
发帖数: 441 | 49 三个主要函数: getNextToken(), buildAST(), eval(). buildAST() 可以是iteration
, eval()是recursion. |
y***x
发帖数: 22 | 50 写了个JavaScript的，想法跟二爷一开始的一样，扫两遍，一遍处理+-， 一遍处理*/
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);
for(var i=0; i
n[i] = getmdnum(n[i]);
}
for(var j=0; j
n[j+1] = cal(n[j], n[j+1], c[j+1]);
}
return n[j];
}
function getmdnum(str){
var n = str.split(/[\*\/]/);
var c = str.split(/[0-9]+/);
if(n.length==1) return n[0]-0;
for(var i=0; i
n[i+1] = cal(n[i], n[i+1], c[i+1]);
}
return n[i];
}
function cal(num1, num2, c){
var n1 = num1 -'0';
var n2 = num2 -'0';
switch(c){
case "+":
return n1+n2;
case "-":
return n1-n2;
case "*":
return n1*n2;
case "/":
return n1/n2;
default:
return "Error";
}
} |
|
|
w********p
发帖数: 948 | 51 我在隔壁也问了一句这个，被人华丽丽的鄙视了 说是学过compiler课。
低头确实还给老师了。
stack 和cursive 都写了下，还是stack思路清晰简洁。
看看思路，code未必是bug free 的。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
|
f*******7
发帖数: 943 | 52 题目一出，我就傻眼了，就知道完蛋了。。。
这题目正好是隔壁BB Onsite面经第二题
给一个表达式，计算返回值，不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天，问对方，对吗？ 多方说，你说呢。。。
祝大家好运吧，哪个大牛给个链接 |
p*****2
发帖数: 21240 | 53 看了一下。这题你怎么做的？
感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。 |
a***o
发帖数: 1182 | 54 stack就行了,或者搞个temp variable
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
|
h*******0
发帖数: 270 | 55 2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
recursive。 我说recursive不好，被华丽丽的鄙视了。。。
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
|
p*****2
发帖数: 21240 | 56
stack更简单吗？
【在 a***o 的大作中提到】
: stack就行了,或者搞个temp variable
|
p*****2
发帖数: 21240 | 57
recursive怎么搞呀？
【在 h*******0 的大作中提到】
: 2爷您的想法和我之前onsite BB的想法一样。。 结果面试官压根不屌我。 必须用
: recursive。 我说recursive不好，被华丽丽的鄙视了。。。
|
f*******7
发帖数: 943 | 58 二爷这题我没见过，硬着头皮写recursive，思路都不对，今天就问了这一题。。。
有相关讲解的链接吗？
【在 p*****2 的大作中提到】
: 看了一下。这题你怎么做的？
: 感觉扫两遍就可以了吧？第一遍算乘除，第二遍算加减。
|
h*******0
发帖数: 270 | 59 我当时也没想出来。 然后我和他说，我这个方法比recursive好。。 我说recursive可
能会out of memory。 人家根本不同意我的说法。
【在 p*****2 的大作中提到】
:
: recursive怎么搞呀？
|
h*******0
发帖数: 270 | 60 我觉得如果见到没见过的题就要赶紧研究。。 弄不好就是你下一道题。。 这题其实挺
不好写的
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
|
|
|
p*****2
发帖数: 21240 | 61
我大概的想法
1000-5*6/3*2+1
用个双向链表
1000 - 5 * 6 / 3 * 2 + 1
第一遍算乘除， 比如 看到第一个 ＊ 就把prev * next 然后把5*6拿掉，把结果30放
进去，就成了
1000 - 30 / 3 * 2 + 1
第二遍算加减就从头算到尾就可以了
想想有没有什么更简单的办法。
【在 f*******7 的大作中提到】
: 二爷这题我没见过，硬着头皮写recursive，思路都不对，今天就问了这一题。。。
: 有相关讲解的链接吗？
|
a***o
发帖数: 1182 | 62 搞俩variable就行了,一个存之前的数,
一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数
【在 p*****2 的大作中提到】
:
: 我大概的想法
: 1000-5*6/3*2+1
: 用个双向链表
: 1000 - 5 * 6 / 3 * 2 + 1
: 第一遍算乘除， 比如 看到第一个 ＊ 就把prev * next 然后把5*6拿掉，把结果30放
: 进去，就成了
: 1000 - 30 / 3 * 2 + 1
: 第二遍算加减就从头算到尾就可以了
: 想想有没有什么更简单的办法。
|
p****e
发帖数: 3548 | 63 搞了个复杂的。。
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
bool OpHigherOrder(char c1, char c2)
{
if(c1 != '(' && c2 == ')')
return true;
else if(c1 == '(')
return false;
else if((c1 == '*' || c1 == '/'))
return true;
else if((c1 == '+' || c1 == '-') && (c2 == '+' || c2 == '-'))
return true;
else
return false;
}
double CalOp(double e1, char op, double e2)
{
switch(op)
{
case '+':
return e1 + e2;
case '-':
return e1 - e2;
case '*':
return e1 * e2;
case '/':
return e1 / e2;
}
}
double CalExpression(string a)
{
stack num;
stack op;
int numpos = 0;
for(int i = 0; i < a.length(); i++)
{
if(a[i] == ' ')
{
a.erase(i, 1);
i--;
continue;
}
if((a[i]>='0' && a[i]<='9') || a[i] == '.')
{
continue;
}
if(a[i] == '(')
{
op.push('(');
numpos = i + 1;
continue;
}
if(numpos < i)
{
num.push(atof(a.substr(numpos, i - numpos).c_str()));
}
while(op.size() > 0 && num.size()>1)
{
if(OpHigherOrder(op.top(), a[i]))
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
else
{
break;
}
}
if(a[i] == ')')
{
op.pop();
}
else
op.push(a[i]);
numpos = i + 1;
}
if(numpos < a.length())
num.push(atof(a.substr(numpos).c_str()));
while(op.size() > 0 && num.size()>1)
{
double right = num.top();
num.pop();
double left = num.top();
num.pop();
num.push(CalOp(left, op.top(), right));
op.pop();
}
return num.top();
}
int main() {
// Start typing your code here...
string s("12+5*62/2-3*(5+3*(5+6))");
cout << CalExpression(s) << endl;
return 0;
} |
p*****2
发帖数: 21240 | 64 1000-5*6/3*2+1
recursion的话
1000 － 然后往后找到 ＋， － 或者end
变成
1000- f(5*6/3*2) + 1
主要是纪录＋－的位置。比如上边的例子，4 13
然后分段算 f(0,3) - f(5, 12) + f(14) |
h*******8
发帖数: 29 | |
p*****2
发帖数: 21240 | 66
应该可以。就是写起来不知道是不是容易bug free。你可以写写看看。
【在 a***o 的大作中提到】
: 搞俩variable就行了,一个存之前的数,
: 一个存当前的数,碰到乘除,更新当前的数,碰到加减更新之前的数
|
o***d
发帖数: 313 | 67 我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
敏的书
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
|
o***d
发帖数: 313 | 68 另外,这个我在careercup上见过google也考过似乎
【在 o***d 的大作中提到】
: 我记得这个是我在国内尚数据结构时stack的李子(当然可能各个学校不一样),参考严蔚
: 敏的书
|
b*****u
发帖数: 648 | 69 试着写了一个递归的
思路： 每个recursion的开始有一个factor，一个当前operand和一个之前乘/除号
首先把operand = operand 乘除 factor
然后，如果下一符号是加减，则返回 operand 加减下一recursion（factor=1， 乘）
如果下一符号是乘除，则返回下一recursion (factor=当前operand, 下一符号）
(on a second thought, 这个其实也就是实现了一个stack的功能，递归即stack)
#include "stdafx.h"
#include
#include
#include
using namespace std;
int stringCalculator(string input, int factor, char sign)
{
int len = input.length();
if (len == 0) return 0;
int i = 0;
while (i< len && input[i]>='0' && input[i]<='9')
{
++i;
}
int rightEnd = min (len, i);
int operand = atoi(input.substr(0,rightEnd).c_str());
if (sign == '*')
operand *= factor;
else
operand /= factor;
if (i == len)
return operand;
else
{
switch (input[i])
{
case '+':
return operand+stringCalculator(input.substr(i+1), 1, '*');
case '-':
return operand-stringCalculator(input.substr(i+1), 1, '*');
default:
return stringCalculator(input.substr(i+1), operand, input[i]);
break;
}
}
}
int calculator (string input)
{
return stringCalculator(input,1,'*');
}
int _tmain(int argc, _TCHAR* argv[])
{
string test = "1+2*3";
cout << calculator (test);
cin.get();
return 0;
} |
m*****1
发帖数: 147 | 70 电面考这个，要求有点高啊，写计算器是以前学做编译原理搞语法和词法分析的小
project哎 |
|
|
w****x
发帖数: 2483 | 71 int mul(const char*& p);
int num(const char*& p);
int Add(const char*& p)
{
int res = mul(p);
while (*p == '+' || *p == '-')
{
if (*p == '+')
res += mul(++p);
else
res -= mul(++p);
}
return res;
}
int mul(const char*& p)
{
int res = num(p);
while (*p == '*' || *p == '/')
{
if (*p == '*')
res *= num(++p);
else
res /= num(++p);
}
return res;
}
int num(const char*& p)
{
bool bNeg = false;
if (*p == '-')
{
bNeg = true;
p++;
}
int res = 0;
while (*p >= '0' && *p <= '9')
res = res*10 + *p++ - '0';
return bNeg ? -res : res;
}
递归下降
Add = mul | (+- mul)*
mul = num | (+- num)*
num = (+-)[0-9]* |
j*****y
发帖数: 1071 | 72 int value(int a, int b, char c)
{
if(c == '+') return a + b;
if(c == '-') return a - b;
if(c == '*') return a * b;
if(c == '/') return a / b;
}
int expression(vector s)
{
if(s.size() == 0)
{
return 0;
}
stack operand;
stack operators;
operand.push(atoi(s[0].c_str()));
for(int i = 1; i < s.size(); ++i)
{
if(isdigit(s[i][0]))
{
operand.push(atoi(s[i].c_str()));
}
else
{ char c = s[i][0];
if(c == '*' || c == '/')
{
int a = atoi(s[++i].c_str());
a = value(operand.top(), a, c);
operand.pop();
operand.push(a);
}
else
{
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
operand.pop();
operand.push(value(a, b, operators.top()));
operators.pop();
operators.push(c);
}
else
{
operators.push(c);
}
}
}
}
if(operand.size() == 2)
{
int b = operand.top();
operand.pop();
int a = operand.top();
return value(a, b, operators.top());
}
else
{
return operand.top();
}
}
感觉不用 stack也可以， 因为 stack里面只有一个或者两个 item
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
|
p*****2
发帖数: 21240 | 73 def cal(str:String):Int={
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(i<-0 until operators.length) operators(i) match{
case '+' => result+=numbers(i+1)
case '-' => result-=numbers(i+1)
case '*' => result*=numbers(i+1)
case '/' => result/=numbers(i+1)
}
result
}
def solve(str:String):Int={
val plusminus= -1 +: (for(i<-0 until str.length if str(i)=='+' ||
str(i)=='-') yield i)
var sb=new StringBuilder()
for(i<-1 until plusminus.length){
sb.append(cal(str.slice(plusminus(i-1)+1,plusminus(i))))
sb.append(str(plusminus(i)))
}
sb.append(cal(str.slice(plusminus.last+1, str.length)))
cal(sb.toString)
} |
h*******0
发帖数: 270 | 74 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
【在 w****x 的大作中提到】
: int mul(const char*& p);
: int num(const char*& p);
: int Add(const char*& p)
: {
: int res = mul(p);
: while (*p == '+' || *p == '-')
: {
: if (*p == '+')
: res += mul(++p);
: else
|
q********s
发帖数: 1032 | 75 这个不是逆波兰吗？
★ 发自iPhone App: ChineseWeb 7.8
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
|
a***o
发帖数: 1182 | 76 写的漂亮,可能C比较简洁
【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
|
e****e
发帖数: 418 | 77 凑个热闹!
public int calculate( String[] in, int sIdx ) {
if ( sIdx == in.length - 1)
return toInt( in[sIdx] );
int addOrMinus = getAddOrMinusSign( in[sIdx + 1] );
if ( addOrMinus != 0 ) {
if ( sIdx + 2 == in.length - 1 || getAddOrMinusSign( in[sIdx + 3] ) !=
0 ) {
in[sIdx+2] = toStr( toInt( in[sIdx] ) + addOrMinus*toInt( in[sIdx+
2] ) );
return calculate( in, sIdx + 2 );
} else {
calMulOrDivAndSetBack( in, sIdx+2 );
in[sIdx+3] = in[sIdx+1];
in[sIdx+2] = in[sIdx];
return calculate( in, sIdx + 2 );
}
}
calMulOrDivAndSetBack( in, sIdx );
return calculate( in, sIdx + 2 );
}
private int getAddOrMinusSign( String s ){
if ( "+".equals( s ) )
return 1;
else if ( "-".equals( s ) )
return -1;
return 0;
}
private void calMulOrDivAndSetBack( String[] in, int idx ) {
if ( "*".equals( in[idx + 1] ) )
in[idx+2] = toStr( toInt( in[idx] ) * toInt( in[idx+2] ) );
else
in[idx+2] = toStr( toInt( in[idx] ) / toInt( in[idx+2] ) );
}
private int toInt( String s ){
return Integer.parseInt( s );
}
private String toStr( Integer i ) {
return Integer.toString( i );
} |
w****x
发帖数: 2483 | 78
可能因为我比较帅吧
【在 h*******0 的大作中提到】
: 为啥感觉你代码写的这么优美呢？ 难道是排版排的好？ ：）
|
l*****a
发帖数: 14598 | 79 看linkedin不像啊
【在 w****x 的大作中提到】
:
: 可能因为我比较帅吧
|
w****x
发帖数: 2483 | 80
等等，我马上换成刘德华的
【在 l*****a 的大作中提到】
: 看linkedin不像啊
|
|
|
s*********s
发帖数: 140 | 81 贴个java recursive的吧。
float compute(String exp) {
if(exp == null || exp.length() == 0) return 0;
int plusPos = exp.indexOf('+');
int minusPos = exp.indexOf('-');
if(plusPos < 0 && minusPos < 0) return convert(exp);
if(plusPos < 0 || (minusPos > 0 && minusPos < plusPos))
return convert(exp.substring(0, minusPos)) - compute(exp.
substring(minusPos+1));
if(minusPos < 0 || (plusPos > 0 && plusPos < minusPos))
return convert(exp.substring(0, plusPos)) + compute(exp.
substring(plusPos+1));
return 0;
}
float convert(String exp){
float res = 1;
float curr = 0;
boolean isProduct = true;
for(int i = 0; i < exp.length(); i++){
if(exp.charAt(i) == '*' || exp.charAt(i) == '/'){
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is
0");
else res = res/curr;
}
curr = 0;
isProduct = (exp.charAt(i) == '*');
} else {
curr = curr * 10 + (float)(exp.charAt(i) - '0');
}
}
if(isProduct)
res = res * curr;
else {
if(curr == 0)
throw new IllegalArgumentException("Denominator is 0");
else res = res/curr;
}
return res;
} |
x*******6
发帖数: 262 | 82 先把表达式转换成operand和operator的string[],再转换成postfix notation，最后用
一个stack来帮助计算 |
p*****2
发帖数: 21240 | 83
这个看起来不错。
【在 w****x 的大作中提到】
: int mul(const char*& p);
: int num(const char*& p);
: int Add(const char*& p)
: {
: int res = mul(p);
: while (*p == '+' || *p == '-')
: {
: if (*p == '+')
: res += mul(++p);
: else
|
s****0
发帖数: 117 | |
l*********8
发帖数: 4642 | 85 double readNumber(const char * &str) {
double num;
sscanf(str, "%lf", &num);
for (++str; isdigit(*str) || *str == '.'; ++str)
;
return num;
}
double calculate(const char * str) {
if (*str == '\0') return 0.0;
double result = 1.0;
char op = '*';
while (op == '*' || op == '/') {
if (op == '*')
result *= readNumber(str);
else
result /= readNumber(str);
op = *str++;
}
return result + calculate(--str);
} |
l*********8
发帖数: 4642 | 86 测试案例：
-3-4.3+5.05*2/4-4.10/5+3 = -2.595
【在 l*********8 的大作中提到】
: double readNumber(const char * &str) {
: double num;
: sscanf(str, "%lf", &num);
: for (++str; isdigit(*str) || *str == '.'; ++str)
: ;
: return num;
: }
: double calculate(const char * str) {
: if (*str == '\0') return 0.0;
: double result = 1.0;
|
l*******b
发帖数: 2586 | 87 学习了...发愁那个减号怎么处理呢...原来是sscanf...哈哈
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
|
s****0
发帖数: 117 | 88 package myutil;
import java.util.Scanner;
import java.util.Stack;
public class ParseExp {
Stack oprand = new Stack();
Stack oprator = new Stack();
static int[] code = new int[256];
static {
code['+'] = 10;
code['-'] = 11;
code['*'] = 20;
code['/'] = 21;
code['^'] = 30;
code['$'] = 0;
code['('] = 100;
code[')'] = 1;
}
public ParseExp() {
}
public Integer parse(String e) {
Scanner s = new Scanner(e + " $");
oprator.push(-1);
while (true) {
if (s.hasNextInt()) {
oprand.push(s.nextInt());
} else if (s.hasNext("[-$+*/^()]")) {
int optr = code[s.next(".").charAt(0)];
while (!oprator.isEmpty() && oprator.peek() > optr) {
int y = oprand.pop();
int x = oprand.pop();
switch (oprator.pop()) {
case 10:
oprand.push(x + y);
break;
case 11:
oprand.push(x - y);
break;
case 20:
oprand.push(x * y);
break;
case 21:
oprand.push(x * y);
break;
case 30:
oprand.push((int) Math.pow(x, y));
break;
}
}
if (optr == 0)
break;
if (optr == 100) {
oprator.push(1);
continue;
} else if (optr == 1) {
oprator.pop();
continue;
} else
oprator.push(optr);
} else {
System.out.println(s.next());
}
}
return oprand.peek();
}
public static void main(String[] args) {
ParseExp p = new ParseExp();
for (String e : new String[] { "1 + 1", "1 + 2 * 3", "1 * 2 + 3",
"1 + 2 * 3 + 4", "2 ^ 8 + 1 * 4", "1 * 4 + 2 ^ 8 - 4",
"( 2 + 3 ) * ( 4 + 6 ) ^ 2" }) {
System.out.println(e + " = " + p.parse(e));
}
}
} |
M******l
发帖数: 479 | 89 逆波兰表达式吧？用个stack就行了，两年前面试被问过，当时居然正好复习到了～～
http://baike.baidu.com/view/552648.htm
【在 f*******7 的大作中提到】
: 题目一出，我就傻眼了，就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式，计算返回值，不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天，问对方，对吗？ 多方说，你说呢。。。
: 祝大家好运吧，哪个大牛给个链接
|
c*****a
发帖数: 808 | |
|
|
p*****2
发帖数: 21240 | 91
longway又出手了。
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
|
H****s
发帖数: 247 | 92 还是这个牛啊！
【在 l*********8 的大作中提到】
: 测试案例：
: -3-4.3+5.05*2/4-4.10/5+3 = -2.595
|
p*****2
发帖数: 21240 | 93
longway的代码向来都是最简洁的。
【在 H****s 的大作中提到】
: 还是这个牛啊！
|
e****e
发帖数: 418 | 94 写了一个infix to postfix，实现起来简单, 不知道思路还真不好想，面试的时候我肯
定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
public List toPostfix(String[] in) {
List pf = new ArrayList();
Stack stack = new Stack();
for ( String s : in ) {
int p = getPrecedence( s );
if ( p == 0 )
pf.add( s );
else if ( stack.empty() )
stack.push( s );
else {
while( !stack.isEmpty() && getPrecedence( stack.peek() ) >= p )
pf.add( stack.pop() );
stack.push( s );
}
}
while( !stack.isEmpty() )
pf.add( stack.pop() );
return pf;
}
private int getPrecedence(String s) {
switch( s ) {
case "*": return 2;
case "/": return 2;
case "+": return 1;
case "-": return 1;
default : return 0;
}
}
【在 M******l 的大作中提到】
: 逆波兰表达式吧？用个stack就行了，两年前面试被问过，当时居然正好复习到了～～
: http://baike.baidu.com/view/552648.htm
|
p*****2
发帖数: 21240 | 95
这东西没搞过。回头看看。
【在 e****e 的大作中提到】
: 写了一个infix to postfix，实现起来简单, 不知道思路还真不好想，面试的时候我肯
: 定想不出来。逆波兰表达式(postfix)evaluation是常见题，我就不贴了.
: public List toPostfix(String[] in) {
: List pf = new ArrayList();
: Stack stack = new Stack();
: for ( String s : in ) {
: int p = getPrecedence( s );
: if ( p == 0 )
: pf.add( s );
: else if ( stack.empty() )
|
l*********8
发帖数: 4642 | 96 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
|
d********f
发帖数: 43471 | 97 20年前你这么回答可能还行
【在 h*******0 的大作中提到】
: 我当时也没想出来。 然后我和他说，我这个方法比recursive好。。 我说recursive可
: 能会out of memory。 人家根本不同意我的说法。
|
n***e
发帖数: 723 | 98 哈哈，这个牛！居然能这么处理。
【在 l*********8 的大作中提到】
: 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
|
I**********s
发帖数: 441 | 99 最喜欢 wwwyhx的解法: recursive descent.
我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
#include
#include // for pow()
using namespace std;
struct Node {
double val;
char op;
int op_prec; // precedence of operator
int type; // 0 - operand, 1 - operator
Node * left;
Node * right;
Node(double _val, char _op, int _type) : val(_val), op(_op),
type(_type), left(NULL), right(NULL) {}
};
class Solution {
private:
int prec_base;
const char * p0; // record start position of input string.
void err(char * msg, const char * p) {
printf("input error: %s, at input position %d\n", msg, p - p0);
printf("%s\n", p0);
for (int i = 0, len = p - p0; i < len; ++ i) putchar(' ');
printf("^\n");
exit(1);
}
void dump_node(Node * n) {
if (n->type == 0) printf(" %.1lf ", n->val);
else printf(" %c ", n->op);
}
void dump(Node * n) {
if (! n) return;
if (! n->left && ! n->right) {
dump_node(n);
return;
}
printf("(");
dump(n->left);
dump_node(n);
dump(n->right);
printf(")");
}
int prec(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
if (op == '^') return 3;
return 0;
}
int isOp(char c) {
return (c == '+' || c == '-' || c == '*' ||
c == '/' || c == '^');
}
int isDigit(char c) { return c >= '0' && c <= '9'; }
// type - desired type of new token. 0 - operand, 1 - operator.
Node * getNextToken(const char *& input, int type) {
const int prec_base_inc = 4; // 1 + max(op prec)
while (isspace(*input)) ++ input; // skips spaces.
if (! *input) return NULL; // end of input.
while (*input == '(') {
prec_base += prec_base_inc;
++ input;
}
// check if is desired type.
if (! ((type == 1 && isOp(*input) ) ||
(type == 0 && (isDigit(*input) || *input == '+' ||
*input== '-' || *input=='.'))) ) {
err("wrong type of operand/operator", input);
}
Node * n;
if (type == 1) { // operator.
n = new Node(0, *input, type);
n->op_prec = prec(n->op) + prec_base;
++ input;
}
else { // type == 0: operand.
double val;
// sscanf requires no space between sign and value.
sscanf(input, "%lf", &val);
n = new Node(val, 0, type);
if (*input == '+' || *input == '-') ++ input;
if (! (isDigit(*input) || *input == '.')) {
err("incomplete number", input);
}
bool dot_used = false; // allow only one dot.
while ( isDigit(*input) || (*input == '.' && !dot_used)) {
if (*input == '.') dot_used = true;
++ input;
}
while (*input == ')') {
prec_base -= prec_base_inc;
++ input;
}
}
return n;
}
void buildAST(const char * input, Node *& root) {
root = getNextToken(input, 0);
while (1) {
Node * opt = getNextToken(input, 1);
if (! opt) return; // end of input.
Node * opd = getNextToken(input, 0);
if (root->type == 0 || opt->op_prec <= root->op_prec) {
opt->left = root;
opt->right = opd;
root = opt;
} else {
Node * n = root;
while (1) {
if (n->right->type == 0 ||
opt->op_prec <= n->right->op_prec) {
opt->left = n->right;
opt->right = opd;
n->right = opt;
break;
} else {
n = n->right;
}
} // end of while
} // end of if
} // end of while
}
double eval(Node * t) {
if (! t) return 0;
if (t->type == 0) return t->val; // t is operand.
// t is operator.
if (t->op == '+') return eval(t->left) + eval(t->right);
if (t->op == '-') return eval(t->left) - eval(t->right);
if (t->op == '*') return eval(t->left) * eval(t->right);
if (t->op == '/') return eval(t->left) / eval(t->right);
if (t->op == '^') return pow(eval(t->left), eval(t->right));
}
public:
Solution() { prec_base = 0; }
~Solution() { /* destroy AST. */ }
double calc(const char * s) {
p0 = s; // record start pointer position.
Node * p = NULL;
buildAST(s, p);
dump(p); puts("");
return eval(p);
}
};
int main() {
const char * input = "(1 + 2)*((3-1)- 3.5) + 4^2";
Solution s;
cout << "Solution 1: " << s.calc(input) << endl;
return 0;
} |
I**********s
发帖数: 441 | 100 三个主要函数: getNextToken(), buildAST(), eval(). buildAST() 可以是iteration
, eval()是recursion. |
|
|
y***x
发帖数: 22 | 101 写了个JavaScript的，想法跟二爷一开始的一样，扫两遍，一遍处理+-， 一遍处理*/
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);
for(var i=0; i
n[i] = getmdnum(n[i]);
}
for(var j=0; j
n[j+1] = cal(n[j], n[j+1], c[j+1]);
}
return n[j];
}
function getmdnum(str){
var n = str.split(/[\*\/]/);
var c = str.split(/[0-9]+/);
if(n.length==1) return n[0]-0;
for(var i=0; i
n[i+1] = cal(n[i], n[i+1], c[i+1]);
}
return n[i];
}
function cal(num1, num2, c){
var n1 = num1 -'0';
var n2 = num2 -'0';
switch(c){
case "+":
return n1+n2;
case "-":
return n1-n2;
case "*":
return n1*n2;
case "/":
return n1/n2;
default:
return "Error";
}
} |
w********p
发帖数: 948 | 102 我在隔壁也问了一句这个，被人华丽丽的鄙视了 说是学过compiler课。
低头确实还给老师了。
stack 和cursive 都写了下，还是stack思路清晰简洁。
看看思路，code未必是bug free 的。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
|
d*******r
发帖数: 14 | 103 先转换成postfix再用stack来实现就容易很多吧。 |
u*****o
发帖数: 1224 | |
n****e
发帖数: 678 | 105 这code，店面写出来不太现实吧。。。
考.
【在 I**********s 的大作中提到】
: 最喜欢 wwwyhx的解法: recursive descent.
: 我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
: 号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
: 及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
: #include
: #include // for pow()
: using namespace std;
: struct Node {
: double val;
: char op;
|
z*********8
发帖数: 2070 | 106 我觉得是啊， coding很简单
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
|
V*********r
发帖数: 666 | 107 >>> s = "1000-5*6/3*2+1"
>>> eval(s)
981 |
s********u
发帖数: 1109 | 108 stack 用来做postfix简单，prefix要用两个或者倒序遍历字符串。没看出写中缀用
stack很简单
【在 z*********8 的大作中提到】
: 我觉得是啊， coding很简单
|
s********u
发帖数: 1109 | 109 我自己小结的是，面试碰到：
1.prefix即波兰表达式，用递归最方便（因为操作符和操作数不是一种类型，操作符也
没有一种对应的文件类型，所以把操作符push进stack稍微麻烦点）；
2.postfix即逆波兰表达式，用stack最方便（因为总是先碰到操作数，不用push操作符
）。
3.infix即中缀表达式，不要求括号的话用longway大侠的方法，要求的话太麻烦了gg。 |
r********7
发帖数: 102 | 110 之前有个人 总结了 ebay 板上所有面经，其中就有这道题。 给出的解决方法就是
longway的那个。
楼主不好好刷题，可惜了。。 能说下是哪个组吗？ |
|
|
t***t
发帖数: 6066 | 111 这个是典型的编译原理的题。用计算表达式的方法做，其实不难。每个symbol要么是
operator，要么是operand。operator有优先级。看优先级决定入栈或出栈。 |
s********u
发帖数: 1109 | 112 汗。。。首先，请看一下lz发帖的时间；其次，那个总结是我写的，然后解决方法就是
贴了longway的这个。。。所以前因后果反了哈哈
【在 r********7 的大作中提到】
: 之前有个人 总结了 ebay 板上所有面经，其中就有这道题。 给出的解决方法就是
: longway的那个。
: 楼主不好好刷题，可惜了。。 能说下是哪个组吗？
|
s****x
发帖数: 15 | 113 刚刚试了一下，感觉还可以哈
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
|
r********7
发帖数: 102 | 114 晕，那这帖子 怎么现在被顶到这么靠前了呢？ 我的错。。
【在 s********u 的大作中提到】
: 汗。。。首先，请看一下lz发帖的时间；其次，那个总结是我写的，然后解决方法就是
: 贴了longway的这个。。。所以前因后果反了哈哈
|
m********c
发帖数: 105 | 115 这个写的真的很好啊！
【在 l*********8 的大作中提到】
: 谢谢！ 这道题目， 如果包含括号和^,那么用逆波兰式应该是经典的解法。但看楼主的
: 面经，面试官似乎是把题目简化了，并期望一个简单些的解答。
|
