f*7
2 楼
题目一出,我就傻眼了,就知道完蛋了。。。
这题目正好是隔壁BB Onsite面经第二题
给一个表达式,计算返回值,不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天,问对方,对吗? 多方说,你说呢。。。
祝大家好运吧,哪个大牛给个链接
这题目正好是隔壁BB Onsite面经第二题
给一个表达式,计算返回值,不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天,问对方,对吗? 多方说,你说呢。。。
祝大家好运吧,哪个大牛给个链接
c*a
3 楼
成交量为0的飘过。。。
p*2
4 楼
看了一下。这题你怎么做的?
感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。
感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。
f*n
7 楼
偶这一两天也是啥客人都没有。
R*g
9 楼
我也是0
p*e
20 楼
搞了个复杂的。。
// 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;
}
// 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
stack
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
21 楼
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)
recursion的话
1000 - 然后往后找到 +, - 或者end
变成
1000- f(5*6/3*2) + 1
主要是纪录+-的位置。比如上边的例子,4 13
然后分段算 f(0,3) - f(5, 12) + f(14)
h*8
22 楼
尝试构造一个对应的AST?不知道可不可以
b*u
26 楼
试着写了一个递归的
思路: 每个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;
}
思路: 每个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
27 楼
电面考这个,要求有点高啊,写计算器是以前学做编译原理搞语法和词法分析的小
project哎
project哎
w*x
28 楼
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]*
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
29 楼
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"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接
{
if(c == '+') return a + b;
if(c == '-') return a - b;
if(c == '*') return a * b;
if(c == '/') return a / b;
}
int expression(vector
{
if(s.size() == 0)
{
return 0;
}
stack
stack
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
30 楼
def cal(str:String):Int={
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(icase '+' => 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(istr(i)=='-') yield i)
var sb=new StringBuilder()
for(isb.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)
}
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(icase '+' => 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(istr(i)=='-') yield i)
var sb=new StringBuilder()
for(isb.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)
}
e*e
34 楼
凑个热闹!
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 );
}
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 );
}
s*s
38 楼
贴个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;
}
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
39 楼
先把表达式转换成operand和operator的string[],再转换成postfix notation,最后用
一个stack来帮助计算
一个stack来帮助计算
s*0
41 楼
向 Edsger Dijkstra 先生致敬:
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
l*8
42 楼
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);
}
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
43 楼
测试案例:
-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;
-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;
s*0
45 楼
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));
}
}
}
import java.util.Scanner;
import java.util.Stack;
public class ParseExp {
Stack
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
46 楼
逆波兰表达式吧?用个stack就行了,两年前面试被问过,当时居然正好复习到了~~
http://baike.baidu.com/view/552648.htm
【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接
http://baike.baidu.com/view/552648.htm
【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接
e*e
51 楼
写了一个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
定想不出来。逆波兰表达式(postfix)evaluation是常见题,我就不贴了.
public List
List
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
52 楼
这东西没搞过。回头看看。
【在 e****e 的大作中提到】
: 写了一个infix to postfix,实现起来简单, 不知道思路还真不好想,面试的时候我肯
: 定想不出来。逆波兰表达式(postfix)evaluation是常见题,我就不贴了.
: public List
: List
: Stack
: for ( String s : in ) {
: int p = getPrecedence( s );
: if ( p == 0 )
: pf.add( s );
: else if ( stack.empty() )
I*s
56 楼
最喜欢 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;
}
我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
#include
#include
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
57 楼
三个主要函数: getNextToken(), buildAST(), eval(). buildAST() 可以是iteration
, eval()是recursion.
, eval()是recursion.
y*x
58 楼
写了个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";
}
}
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);
for(var i=0; i
}
for(var j=0; j
}
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
}
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
59 楼
我在隔壁也问了一句这个,被人华丽丽的鄙视了 说是学过compiler课。
低头确实还给老师了。
stack 和cursive 都写了下,还是stack思路清晰简洁。
看看思路,code未必是bug free 的。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
低头确实还给老师了。
stack 和cursive 都写了下,还是stack思路清晰简洁。
看看思路,code未必是bug free 的。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
f*7
60 楼
题目一出,我就傻眼了,就知道完蛋了。。。
这题目正好是隔壁BB Onsite面经第二题
给一个表达式,计算返回值,不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天,问对方,对吗? 多方说,你说呢。。。
祝大家好运吧,哪个大牛给个链接
这题目正好是隔壁BB Onsite面经第二题
给一个表达式,计算返回值,不带括号
例子
"7-12/6"
"1000-5*6/3*2+1"
写了半天,问对方,对吗? 多方说,你说呢。。。
祝大家好运吧,哪个大牛给个链接
p*2
61 楼
看了一下。这题你怎么做的?
感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。
感觉扫两遍就可以了吧?第一遍算乘除,第二遍算加减。
p*e
71 楼
搞了个复杂的。。
// 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;
}
// 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
stack
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
72 楼
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)
recursion的话
1000 - 然后往后找到 +, - 或者end
变成
1000- f(5*6/3*2) + 1
主要是纪录+-的位置。比如上边的例子,4 13
然后分段算 f(0,3) - f(5, 12) + f(14)
h*8
73 楼
尝试构造一个对应的AST?不知道可不可以
b*u
77 楼
试着写了一个递归的
思路: 每个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;
}
思路: 每个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
78 楼
电面考这个,要求有点高啊,写计算器是以前学做编译原理搞语法和词法分析的小
project哎
project哎
w*x
79 楼
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]*
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
80 楼
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"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接
{
if(c == '+') return a + b;
if(c == '-') return a - b;
if(c == '*') return a * b;
if(c == '/') return a / b;
}
int expression(vector
{
if(s.size() == 0)
{
return 0;
}
stack
stack
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
81 楼
def cal(str:String):Int={
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(icase '+' => 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(istr(i)=='-') yield i)
var sb=new StringBuilder()
for(isb.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)
}
val numbers=str.split("[+-/*]").map(_.toInt)
val operators=str.filterNot(_.isDigit)
var result=numbers(0)
for(icase '+' => 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(istr(i)=='-') yield i)
var sb=new StringBuilder()
for(isb.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)
}
e*e
85 楼
凑个热闹!
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 );
}
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 );
}
s*s
89 楼
贴个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;
}
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
90 楼
先把表达式转换成operand和operator的string[],再转换成postfix notation,最后用
一个stack来帮助计算
一个stack来帮助计算
s*0
92 楼
向 Edsger Dijkstra 先生致敬:
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
l*8
93 楼
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);
}
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
94 楼
测试案例:
-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;
-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;
s*0
96 楼
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));
}
}
}
import java.util.Scanner;
import java.util.Stack;
public class ParseExp {
Stack
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
97 楼
逆波兰表达式吧?用个stack就行了,两年前面试被问过,当时居然正好复习到了~~
http://baike.baidu.com/view/552648.htm
【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接
http://baike.baidu.com/view/552648.htm
【在 f*******7 的大作中提到】
: 题目一出,我就傻眼了,就知道完蛋了。。。
: 这题目正好是隔壁BB Onsite面经第二题
: 给一个表达式,计算返回值,不带括号
: 例子
: "7-12/6"
: "1000-5*6/3*2+1"
: 写了半天,问对方,对吗? 多方说,你说呢。。。
: 祝大家好运吧,哪个大牛给个链接
e*e
102 楼
写了一个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
定想不出来。逆波兰表达式(postfix)evaluation是常见题,我就不贴了.
public List
List
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
103 楼
这东西没搞过。回头看看。
【在 e****e 的大作中提到】
: 写了一个infix to postfix,实现起来简单, 不知道思路还真不好想,面试的时候我肯
: 定想不出来。逆波兰表达式(postfix)evaluation是常见题,我就不贴了.
: public List
: List
: Stack
: for ( String s : in ) {
: int p = getPrecedence( s );
: if ( p == 0 )
: pf.add( s );
: else if ( stack.empty() )
I*s
107 楼
最喜欢 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;
}
我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
#include
#include
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
108 楼
三个主要函数: getNextToken(), buildAST(), eval(). buildAST() 可以是iteration
, eval()是recursion.
, eval()是recursion.
y*x
109 楼
写了个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";
}
}
function getnum(str){
var n = str.split(/[+\-]+/);
var c = str.split(/[0-9\*\/]+/);
for(var i=0; i
}
for(var j=0; j
}
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
}
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
110 楼
我在隔壁也问了一句这个,被人华丽丽的鄙视了 说是学过compiler课。
低头确实还给老师了。
stack 和cursive 都写了下,还是stack思路清晰简洁。
看看思路,code未必是bug free 的。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
低头确实还给老师了。
stack 和cursive 都写了下,还是stack思路清晰简洁。
看看思路,code未必是bug free 的。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
【在 p*****2 的大作中提到】
:
: 这东西没搞过。回头看看。
d*r
111 楼
先转换成postfix再用stack来实现就容易很多吧。
u*o
112 楼
mark一下,赶脚这楼里出手的大牛们很多呀
n*e
113 楼
这code,店面写出来不太现实吧。。。
考.
【在 I**********s 的大作中提到】
: 最喜欢 wwwyhx的解法: recursive descent.
: 我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
: 号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
: 及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
: #include
: #include // for pow()
: using namespace std;
: struct Node {
: double val;
: char op;
考.
【在 I**********s 的大作中提到】
: 最喜欢 wwwyhx的解法: recursive descent.
: 我也写了个, 用的是建造AST, 再evaluate AST. 应该相当完整了: 数字之前可以有+-
: 号, 中间可以有一个小数点. 数字和运算符号之间可以有空格. 可以使用+,-,*,/,^,以
: 及括号. 可以检测错误输入并报出错误位置. 就是比较长, 不适合面试用. 供大家参考.
: #include
: #include
: using namespace std;
: struct Node {
: double val;
: char op;
V*r
115 楼
>>> s = "1000-5*6/3*2+1"
>>> eval(s)
981
>>> eval(s)
981
s*u
117 楼
我自己小结的是,面试碰到:
1.prefix即波兰表达式,用递归最方便(因为操作符和操作数不是一种类型,操作符也
没有一种对应的文件类型,所以把操作符push进stack稍微麻烦点);
2.postfix即逆波兰表达式,用stack最方便(因为总是先碰到操作数,不用push操作符
)。
3.infix即中缀表达式,不要求括号的话用longway大侠的方法,要求的话太麻烦了gg。
1.prefix即波兰表达式,用递归最方便(因为操作符和操作数不是一种类型,操作符也
没有一种对应的文件类型,所以把操作符push进stack稍微麻烦点);
2.postfix即逆波兰表达式,用stack最方便(因为总是先碰到操作数,不用push操作符
)。
3.infix即中缀表达式,不要求括号的话用longway大侠的方法,要求的话太麻烦了gg。
r*7
118 楼
之前有个人 总结了 ebay 板上所有面经,其中就有这道题。 给出的解决方法就是
longway的那个。
楼主不好好刷题,可惜了。。 能说下是哪个组吗?
longway的那个。
楼主不好好刷题,可惜了。。 能说下是哪个组吗?
t*t
119 楼
这个是典型的编译原理的题。用计算表达式的方法做,其实不难。每个symbol要么是
operator,要么是operand。operator有优先级。看优先级决定入栈或出栈。
operator,要么是operand。operator有优先级。看优先级决定入栈或出栈。
相关阅读
弯曲现在总人口有没有有人在Ripple上班的吗?乘BQ的东风,问一下这题怎么答?最近天气转凉,周末大家有啥计划?苏享茂顶级名校通信黄埔北邮毕业,在一线厂子bat当过年老马公, (转载)大部分CS毕业都是找software developer的工作吗?刷题就要达到这种状态--zt版上面向大包刷题的大牛们拿到40万大包以后都干嘛去了刷题已成为码工绕不过的坎?问一个比较简单的数据库问题满屏的刷题大包裹,请问现在弯曲非CS就业情况如何?真诚求教怎么跟LNKD HR拖offer?大波士顿地区找化学分析员80年代, 物理专业可是牛逼专业 (转载)fb设计题老是甲骨文LAYOFF,为什么狗,脸不大量LAYOFF人 (转载)今天咖啡店怎么这么多人?各位觉得:算法高薪马公与奥赛银牌或考清北比哪个难一家据说马上就要IPO的公司给了个offer, 说是给3w股 stock opt工业自动化软件,硬件设计工程师