首页 > 代码库 > LeetCode之逆波兰式求解

LeetCode之逆波兰式求解

计算逆波兰式子:

有效的操作只有 +-*/. 每一个输入不是一个整数就是一个操作符。

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

<span style="font-size:14px;">#include<iostream>
#include<string>
#include<vector>
using namespace std;

const int Max=100;
bool isInt(const string str)
{
  
  if(str[0]=='+'||(str[0]=='-'&&str.size()==1)||str[0]=='*'||str[0]=='/')
   return false;
  else return true;
}
int toInt(string str)
{
   int re=0;
   //cout<<"str: "<<str<<endl;
   for(int i=0;i<str.size();i++)
   {
    re = re*10+ str[i]-'0';
   }
  // cout<<"re: "<<re<<endl;
   return re;
}
int fun(vector<string> &tokens)
{
  double  values[Max]={0};
  int k=0;
  vector<char> oper;
  double result=0;

  for(int i=0;i<tokens.size();i++)
  {
     if(isInt(tokens[i]))
     {
       values[k++]=toInt(tokens[i]);
    
     }else{
      double tmp1=values[--k];
      double tmp2=values[--k];
      char t = tokens[i][0];
      switch(t)
      {
        case '+': result = tmp2 + tmp1; break;
        case '-': result = tmp2 - tmp1; break;
        case '*': result = tmp2 * tmp1; break;
        case '/': result = tmp2 / tmp1; break;
       
      }
        values[k++]=result;
     }
   }
    return result; 
}

int main(){
    string str[5]={"4","13","5","/","+"};
    vector<string> token(str,str+5);
     cout<<fun(token)<<endl;
}</span>

代码中用数组模拟类一个栈的操作。

LeetCode之逆波兰式求解