中缀表达式转后缀表达式（选做）

题目描述
将中缀表达式（infix expression）转换为后缀表达式（postfix expression）。假设中缀表达式中的操作数均以单个英文字母表示，且其中只包含左括号’('，右括号‘)’和双目算术操作符+，-，*， /。

输入描述
表示中缀表达式的一个字符串（其中只包含操作数和操作符和左右括号，不包含任何其他字符），长度不超过100个字符。

输出描述
对应后缀表达式字符串（其中只包含操作数和操作符，不包含任何其他字符）

样例输入

A+B*C-D-E/F
a+(b-c)*d+e/f

样例输出

ABC*+D-EF/-
abc-d*+ef/+

我的答案

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main(){
        stack<char> st;
        st.push('0');
        vector<char> str;
        string tempstr;
        cin>>tempstr;
        str.assign(tempstr.begin(),tempstr.end());
        
        for (int j = 0; j < str.size(); j++){//遍历vector中每个元素
        if((str[j]>='a'&&str[j]<='z')||(str[j]>='A'&&str[j]<='Z')){
              cout<<str[j];
              }
        else if (str[j]=='*'||str[j]=='/'){
            while(st.top()=='*'||st.top()=='/'){
                 cout<<st.top();
                 st.pop();
            }
             st.push(str[j]);
         }
         else if (str[j]=='+'||str[j]=='-'){
            while((st.top()=='*'||st.top()=='/')||(st.top()=='-'||st.top()=='+')){
                 cout<<st.top();
                 st.pop();
            }
             st.push(str[j]);
         }
         else if (str[j]=='('){
              st.push(str[j]);
         }
         else if (str[j]==')'){
            while(st.top()!='('){
                cout<<st.top();
                st.pop();
            }
            st.pop();
         }
        }
        while(st.size()!=1){
            cout<<st.top();
            st.pop();
        }
        cout<<endl;
}

ZHC的答案

#include<iostream>
using namespace std ;
//cout<<fixed<<setprecision(2)<<a;
/*操作数直接输出
操作符入栈，优先级高的可以压住优先级低的，
优先级低的入栈会将优先级高的和同级的依次弹出再入栈
左括号 "(" 入栈直至 右括号")" 入栈才弹出（但不显示），
并在右括号入栈时左括号之上的操作符依次出栈
*/
class Stack{
private:
    char*data; //储存操作符
    int  num;
    int Capacity ;
public:
    Stack(){
     Capacity = 100 ;
    num = 0 ;
    this->data = new char[Capacity];
    }
    ~Stack(){
    delete [] this->data ;
    }
    
    int isop(const char t){ 
    //判断是否为操作符且操作符的优先级 2 */ > 1 +- > 0 () > -1
        if( t=='*' || t=='/') return 3 ;
        else if( t=='+' || t=='-' ) return 2;
        else if( t=='(') return 1 ;
        else if( t==')') return 0 ;
        else return -1;
    }
    
    void pop(char t){
        if( isop(t) != -1 ){
            if(num==0){ data[num] = t ; ++num; }
            else{
                if(isop(t)>isop(data[num-1])){
                    data[num] = t ; ++num;
                }
                else if(isop(t)==1){
                    data[num] = t ; ++num;
                }
                else if(isop(t)==0){
                    while(isop(data[num-1])!=1 && num>0 ){
                        cout<<data[num-1];
                        --num;}
                         --num;//不要输出'('
                }
                else{
                    while(isop(t) <= isop(data[num-1]) && num>0){
                         cout<<data[num-1];
                        --num; }
                    data[num] = t ; ++num;
                }
            }
        }
        else cout<<t;
    }
    void change(string ss){
        for(int i = 0 ; i< ss.size() ; ++i ){
         this->pop( ss.at(i) );
        }
        for(int i = 0 ; i < num ; ++i ){
            cout<<data[num-1-i];
        }
    }
};

int main(){
    Stack exp ;
    string s="";
    cin>>s ;
    exp.change(s);
    return 0 ;
}