Polish Calculator
Infix->Postfix Rules:
- number -> postfix stack
- ( -> opera stack
- ) -> pop opera stack until (
- +-*/ ->
- pop greater or equal priority operators
- push them to postfix stack
- opera stack
class Solution {
public:
int string2Int(const string s){
int result=0;
for(auto c:s){
result=result*10-48+c;
}
return result;
}
vector<string> str2Vector(string s){
vector<string> infix_tokens;
string num;
for(char c:s){
if(c==' ') continue;
if(c>47) num=num+c;
else{
infix_tokens.push_back(num);
num = c;
infix_tokens.push_back(num);
num = "";
}
}
infix_tokens.push_back(num); //last num
for(int i=0;i<infix_tokens.size();i++){
cout<<infix_tokens[i]<<" ";
}
cout<<endl;
return infix_tokens;
}
stack<string> infix2Post(vector<string> infix_tokens){
stack<string> postfix_tokens;
stack<string> opera;
for(auto token:infix_tokens){
if(token =="(") opera.push("(");
else if(token==")"){
while(!opera.empty()&&opera.top()!="("){
postfix_tokens.push(opera.top());
opera.pop();
}
opera.pop(); //"("
}
else if(token=="+"||token=="-"||token=="*"||token=="/"){
if(token=="+"||token=="-"){
while(!opera.empty()&&opera.top()!="("){
postfix_tokens.push(opera.top());
opera.pop();
}
opera.push(token);
}
else{
while(!opera.empty()&&(opera.top()=="*"||opera.top()=="/")){
postfix_tokens.push(opera.top());
opera.pop();
}
opera.push(token);
}
}
else
postfix_tokens.push(token); //num
}
while(!opera.empty()){ //leftover
postfix_tokens.push(opera.top());
opera.pop();
}
return postfix_tokens;
}
int evalPostfix(stack<string> &postfix_tokens){
int value = 0;
if(!postfix_tokens.empty()){
string opera = postfix_tokens.top();
cout<<"opera: "<<opera<<endl;
if(opera == "+"){
postfix_tokens.pop();
int second = evalPostfix(postfix_tokens);
int first = evalPostfix(postfix_tokens);
cout<<first<<" + "<<second<<endl; //test
return first + second;
}
else if(opera == "-"){
postfix_tokens.pop();
int second = evalPostfix(postfix_tokens);
int first = evalPostfix(postfix_tokens);
cout<<first<<" - "<<second<<endl; //test
return first - second;
}
else if(opera == "*"){
postfix_tokens.pop();
int second = evalPostfix(postfix_tokens);
int first = evalPostfix(postfix_tokens);
cout<<first<<" * "<<second<<endl; //test
return first * second;
}
else if(opera == "/"){
postfix_tokens.pop();
int second = evalPostfix(postfix_tokens);
int first = evalPostfix(postfix_tokens);
cout<<first<<" / "<<second<<endl; //test
return first / second;
}
else//num
{
int num = string2Int(opera);
postfix_tokens.pop();
cout<<"num: "<<num<<endl; //test
return num;
}
}
else
{
cout<<"error 2"<<endl;
}
return 0;
}
int calculate(string s) {
vector<string> infix_tokens = str2Vector(s);
stack<string> postfix_tokens = infix2Post(infix_tokens);
int result = evalPostfix(postfix_tokens);
return result;
}
};