Statistic Learning Study
TM
trade mark 商标
Decision Tree
属于判别模型，目标函数是最小正则化的极大似然估计，
Caplat(T)= C(T)+alpha |T|
右侧惩罚项，表示模型复杂度，也即叶子节点个数，前面的训练误差，后面是模型复杂度，如果没有后面的正则项的话，容易过拟合，因此
算法采用ID3和C4.5， 每次进行信息增益比最大的特征选择。
中缀表达式算法已经忘得一干二净了。。。
定义运算符优先级，其中)( 与 #) 与 (# 对于合法的表达式都是不会出现的。
op stack push '#'
while(s[i]!='#' || stop.top()!='#')
{
if( 0-9)
{
get continuous dig and push to num stack
}
else
{
char c=op stack top, cur=s[i]
if(c<cur) op stack push cur, i++
else if(c==cur) op pop //'9' ')'
else
{
num2=num stack pop
num1=num stack pop
op=op stack op
num stack push (num1 op num2)
//notice this do not i++, as cur op should process all pre op that is lower than it
}
}
}
return num stack top
https://leetcode.com/problems/basic-calculator/
代码如下：
class Solution {
public:
string Pri[5]={"=<<<?",
">>><>",
">>><>",
"?<<<=",
">>>?>"};
int index(char op)
{
if(op=='#') return 0;
else if(op=='+') return 1;
else if(op=='-') return 2;
else if(op=='(') return 3;
else return 4;
}
int calculate(string s)
{
s.push_back('#');
int n=s.size();
stack<int> stnum;
stack<char> stop;
stop.push('#');
int i=0;
while(i<n && (s[i]!='#' || stop.top()!='#'))
{
while(i<n && s[i]==' ') i++;
if(i==n) break;
if(isdigit(s[i]))
{
int si=i++;
while(i<n && isdigit(s[i])) i++;
stnum.push(stoi(s.substr(si, i-si)));
}
else
{
char etop=stop.top(), ecur=s[i];
char pri=Pri[index(etop)][index(ecur)];
if(pri=='<')
{
stop.push(ecur);
i++;
}
else if(pri=='=')
{
stop.pop();
i++;
}
else
{
int num2=stnum.top();stnum.pop();
int num1=stnum.top();stnum.pop();
char e=stop.top(); stop.pop();
int ans= ( (e=='+') ? (num1+num2) : (num1-num2));
stnum.push(ans);
}
}
}
//cout<<stnum.size()<<endl;
return stnum.top();
}
} S;