中缀表达式转前缀或后缀并计算结果 2021-04-28

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
using namespace std;
//运算符的优先级 
int get_fast(string op)
{
  int ans=-1;
  switch(op[0]){
    case '+':case '-':ans=1;break;
    case '*':case '/':ans=2;break;
    case '^':ans=3;break;
  }
  return ans;
}
//字符串拆解放入vector 
vector<string> scaner(string s)
{
  vector<string> ans;
  string ops="+-*/^()";
  string t="";
  for(int i=0;i<s.size();i++){
    if(s[i]>='0'&&s[i]<='9') t+=s[i];
    else if(ops.find(s[i])!=string::npos){
      if(t.size()>0) ans.push_back(t);
      t=s[i];
      ans.push_back(t);
      t="";
    }
  }
  if(t.size())ans.push_back(t);
  for(int i=0;i<ans.size();i++)cout<<ans[i];
  cout<<endl; 
  return ans;
}
//中缀表达式转前缀表达式 
/*  初始化：运算符栈和储存中间结果的vector；
*1【反转】遍历中缀表达式;
*2、遇到操作数时,直接将输出到vector;
*3、遇到运算符时,比较其与符号栈顶运算符的优先级;
*   3.1、如果符号栈为空，或者栈顶运算符为右括号")",则直接将此运算符压入符号栈中;
*   3.2、否则,若优先级比栈顶运算符的优先级【高或相等】，则直接将此运算符压入符号栈中;
*   3.3、否则,将符号栈顶的运算符弹出并压入到vector中，再次转入步骤4，与符号栈中新的栈顶运算符相比较;
*4、遇到括号时:
*   4.1、如果是右括号")",则直接压入符号栈中;
*   4.2、如果是左括号"(",则依次弹出符号栈栈顶的运算符并压入vector中,直到遇到右括号")"为止,将括号丢弃;
*5、重复步骤2~4，直到表达式的最左边;
*6、将符号栈中剩余的运算符依次弹出并压入vector中;
*7、【反转】vector即为前缀表达式.
*/
vector<string> infix_Topn(vector<string> exp)
{
  vector<string> ans;
  stack<string> st;
  string op="+-*/^()";
  for(int i=(exp.size()-1);i>=0;i--){//1.【反转】中缀表达式数组
    if(exp[i]==")") st.push(exp[i]);//2.如果是右括号")"，则直接压入符号栈中
    else if(exp[i]=="("){//3.如果是左括号"("，在找到")"之前连续出栈运算符
      while(st.top()!=")") {
        ans.push_back(st.top());
        st.pop();
      }
      st.pop();//弹出")"
    } 
    else if(op.find(exp[i])!=string::npos){//确定是运算符
      while(st.size() && get_fast(exp[i]) < get_fast(st.top())){
        ans.push_back(st.top());
        st.pop();//4.如果栈顶的运算符优先级[大于]当前运算符 栈顶的运算符被连续弹出 
      }
      st.push(exp[i]);
    }
    else ans.push_back(exp[i]);//4、数字直接输出到数组 栈 
  }
  while(st.size()){//5、栈内剩余运算符被连续弹出
    ans.push_back(st.top());
    st.pop();
  }
  cout<<"前缀表达式:";
  for(int i=(ans.size()-1);i>=0;i--)cout<<ans[i];//反转输出前缀表达式 
  cout<<endl;
  return ans;
}
//前缀表达式求值:
//【从右至左】扫描表达式，遇到数字时将数字压入栈，
//遇到运算符，弹出栈顶的2个数用运算符做出计算，并把计算的结果入栈；
//重复上述过程，直到表达式的左端，最后运算得出的值即为表达式的结果。
void topn_calc(vector<string> exp)
{
  stack<int> num;
  string ops="+-*/^";
  for(int i=0;i<exp.size();i++){
    if(ops.find(exp[i])!=string::npos){
      int a=num.top();num.pop();
      int b=num.top();num.pop();
      if(exp[i]=="+")num.push(a+b);
      else if(exp[i]=="-")num.push(a-b);
      else if(exp[i]=="*")num.push(a*b);
      else if(exp[i]=="/")num.push(a/b);
      else if(exp[i]=="^")num.push(pow(a*1.0,b));
    }
    else
      num.push(atoi(exp[i].c_str()));
  }
  cout<<"前缀表达式运算结果:"<<num.top()<<endl;
  //return num.top();
}
//中缀表达式转后缀表达式 
/* 初始化：运算符栈和储存中间结果的vector
*1.从左至右扫描中缀表达式;
*2.遇到操作数时,将其压入vector;
*3.遇到运算符时,比较其与栈顶运算符的优先级：
*  3.1如果栈为空，或栈顶运算符为左括号"(",则直接将此运算符入栈;
*  3.2否则,若优先级比栈顶运算符的【高】，也将运算符压入栈;
*  3.3否则,将栈顶的运算符弹出并压入到vector中，再次转到(4-1)与栈中新的栈顶运算符相比较;
*4.遇到括号时：
*  4.1如果是左括号"(",则直接入栈;
*  4.2如果是右括号")",则依次弹出栈顶运算符,并压入vector,直到遇到左括号为止,将括号丢弃;
*5.重复步骤2至4，直到表达式的最右边;
*6.将S1中剩余的运算符依次弹出并压入vector;
*7.依次输出vector中的元素后缀表达式.
*/
vector<string> infix_Suffix(vector<string> exp)
{
  vector<string> ans;
  stack<string> st;
  string op="+-*/^()";
  for(int i=0;i<exp.size();i++){
    if(exp[i]=="(") st.push(exp[i]);
    else if(exp[i]==")"){
      while(st.top()!="(") {
        ans.push_back(st.top());
        st.pop();
      }
      st.pop();
    } 
    else if(op.find(exp[i])!=string::npos){
      while(st.size() && get_fast(exp[i]) <= get_fast(st.top())){
        ans.push_back(st.top());
        st.pop();
      }
      st.push(exp[i]);
    }
    else ans.push_back(exp[i]);
  }
  while(st.size()){
    ans.push_back(st.top());
    st.pop();
  }
  cout<<"后缀表达式:";
  for(int i=0;i<ans.size();i++)cout<<ans[i];
  cout<<endl;
  return ans;
}
//后缀表达式计算结果 
//从左至右扫描表达式，遇到数字时，将数字压入堆栈;
//遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结果入栈；
//重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
int suffix_calc(vector<string> exp)
{
  stack<int> num;
  string ops="+-*/^";
  for(int i=0;i<exp.size();i++){
    if(ops.find(exp[i])!=string::npos){
      int a=num.top();num.pop();
      int b=num.top();num.pop();
      if(exp[i]=="+")num.push(b+a);
      else if(exp[i]=="-")num.push(b-a);
      else if(exp[i]=="*")num.push(b*a);
      else if(exp[i]=="/")num.push(b/a);
      else if(exp[i]=="^")num.push(pow(b*1.0,a));
    }
    else
      num.push(atoi(exp[i].c_str()));
  }
  cout<<"后缀表达式运算结果:"<<num.top()<<endl;
  return num.top();
}
int main(int argc, char *argv[])
{
  string s="(3+4)*5-6";
  vector<string> vs=scaner(s);//(3+4)*5-6
  vs=infix_Topn(vs);//前缀表达式:-*+3456
  topn_calc(vs);//前缀表达式运算结果:29
  cout<<endl;
  string ss="1+((2+3)*4)-5";
  vector<string> vss=scaner(ss);//1+((2+3)*4)-5
  vss=infix_Suffix(vss);//后缀表达式:123+4*+5-
  suffix_calc(vss);//后缀表达式运算结果:16
  //getline(cin,s);
  return 0;
}