中缀表达式转后缀表达式

思路：
从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出找并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

s = input()
stack = []
res = []
d = {}
d['+'] = 1
d['-'] = 1
d['*'] = 2
d['/'] = 2
for e in s:
    if e in '+-*/':
        while len(stack) > 0 and d[stack[-1]] >= d[e]:
            res.append(stack.pop())
        stack.append(e)
    else:
        res.append(e)
res += stack[::-1]
print("".join(res))

#include<bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    stack<char> S;
    S.push('#');
    map<char,int> M;
    M['#'] = 0;
    M['+'] = 1; M['-'] = 1;
    M['*'] = 2; M['/'] = 2;
    for(auto c : str){
        if(isalpha(c)) cout<<c;
        else{
            while(M[c] <= M[S.top()]){
                cout<<S.top();
                S.pop();
            }
            S.push(c);
        }
    }
    while(S.top()!='#'){
        cout<<S.top();
        S.pop();
    }
    cout<<endl;
    return 0;
}

""""
栈，判断运算优先级
"""
if __name__ == "__main__":
    s = input().strip()
    t_ans, t_opt = [], []
    for i in range(len(s)):
        if s[i] in '+-':
            while t_opt and len(t_ans) >= 2:
                x, y, opt = t_ans.pop(), t_ans.pop(), t_opt.pop()
                t_ans.append(y + x + opt)
            t_opt.append(s[i])
        elif s[i] in '*/':
            if t_opt and t_opt[-1] in '*/' and len(t_ans) >= 2:
                x, y, opt = t_ans.pop(), t_ans.pop(), t_opt.pop()
                t_ans.append(y + x + opt)
            t_opt.append(s[i])
        else:
            t_ans.append(s[i])
    while t_opt and len(t_ans) >= 2:
        x, y, opt = t_ans.pop(), t_ans.pop(), t_opt.pop()
        t_ans.append(y + x + opt)
    print(t_ans[0])

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    if(s.size()==0) 
    {
        cout<<"";
        return 0;
    }
    stack<char> st;
    int i=0;
    while(i<s.size())
    {
        if(s[i]>='a'&&s[i]<='z')
            cout<<s[i++];
        else if(s[i]=='+'||s[i]=='-')
        {
            if(!st.empty()) 
            {
                cout<<st.top();
                st.pop();
            }
            st.push(s[i++]);
        }
        else if(s[i]=='*'||s[i]=='/')
        {
            cout<<s[++i];
            cout<<s[i-1];
            i++;
        }
    }
    if(!st.empty()) 
    {
        cout<<st.top();
        st.pop();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    stack<char> S;
    map<char,int> P;
    P['+'] = P['-'] = 1;
    P['*'] = P['/'] = 2;
    for(int i=0;i<s.length();i++){
        if(isalpha(s[i]))
            cout<<s[i];
        else{
            while(!S.empty() && P[s[i]]<=P[S.top()]){
                cout<<S.top();
                S.pop();
            }
            S.push(s[i]);
        }
    }
    while(!S.empty()){
        cout<<S.top();
        S.pop();
    }
    cout<<endl;
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;

public class middlleToBehind {
    public static String line;
    public static Deque<Character> stack;
    public static HashMap<Character, Integer> map = new HashMap(){
        {
            put('(', 0);
            put('+', 1);
            put('-', 1);
            put('*', 2);
            put('/', 2);
        }
    };
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        while((line = in.readLine()) != null){
            stack = new ArrayDeque<>();
            out.println(compute(line));
        }
        out.flush();
        in.close();
        out.close();
    }
    public static String compute(String line){
        line = line.replaceAll(" ", "");
        char[] strArray = line.toCharArray();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < strArray.length; i++){
            char c = strArray[i];
            if(c >= 'a' && c <= 'z'){
                sb.append(c);
            }else if(c == '('){
                stack.push(c);
            }else if(c == ')'){
                while(!stack.isEmpty() && stack.peek() != '('){
                    sb.append(stack.pop());
                }
                stack.pop();
            }else{
                while(!stack.isEmpty() && map.get(stack.peek()) >= map.get(c)){
                    sb.append(stack.pop());
                }
                stack.push(c);
            }
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.toString();
    }

```

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

int main()
{
    stack<char>st;//符号容器
    string put;//用例容器
    cin>>put;
    vector<int>letNum(50);//建立优先级关系
    letNum['*'] = 1;
    letNum['/'] = 1;
    letNum['+'] = 2;
    letNum['-'] = 2;
    for(size_t i = 0; i<put.size(); i++)
    {
        //若是操作数直接输出
        if(put[i] != '+' && put[i] != '-' 
        && put[i] != '*' && put[i] != '/')
        {
            cout<<put[i];
        }
        //若是符号进行处理
        else
        {
            //保证栈中不为空，至少有一个符号
            if(st.empty())
            {
                st.push(put[i]);
                continue;
            }
            //分两种情况处理
            //1、若栈顶符号优先级低于用例符号，则用例符号入栈
            //2、若栈顶符号优先级高于用例符号，则出栈顶元素，继续对比栈顶符号
            //直到栈顶符号低于用例符号才停止出栈，再将用例符号入栈
            while(!st.empty() && letNum[put[i]] >= letNum[st.top()])
            {
                cout<<st.top();
                st.pop();
            }
            st.push(put[i]);
        }
    }
    //若栈内还有符号，则出栈
    while(!st.empty())
    {
        cout<<st.top();
        st.pop();
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    stack<char> s;
    s.push('#');
    map<char,int> m;
    m['#'] = 0;
    m['+'] = 1,m['-'] = 1;
    m['*'] = 2,m['/'] = 2;
    char c = getchar();
    while(c != '\n'){
        if(isalpha(c)) cout<<c;
        else{
            while(m[c] <= m[s.top()]){
                cout<<s.top();
                s.pop();
            }
            s.push(c);
        }
        c = getchar();
    }
    while(s.top() != '#'){
        cout<<s.top();
        s.pop();
    }
    cout<<endl;
    return 0;
}

var arr=readline().split('');
// 设置权重对象
var obj={'+':1,'-':1,'*':2,'/':2};
// 设置两个栈
var resarr=[];
var temarr=[];
for(var i=0;i<arr.length;i++){
    var len=temarr.length;
    if(!obj[arr[i]]){
        resarr.push(arr[i]);
        continue;
    }else if(temarr[0]){
        for(var m=len-1;m>=0;m--){
            if(obj[arr[i]]<=obj[temarr[m]]){
                resarr.push(temarr[m]);
                temarr.pop();
            }else{
                temarr.push(arr[i])
                break;
            }
        }
        //.此时还需要判断是否temarr不等于[]
        if(temarr.length==0){
            temarr.push(arr[i])
        }
    }else{
        temarr.push(arr[i])
    }
}
// 最后还需要清空temarr
if(temarr.length>0){
    for(var k=temarr.length-1;k>=0;k--){
        resarr.push(temarr[k])
    }
}
console.log(resarr.join(''))

• 第一次遇到时间复杂度过大不通过的问题，求分析

• 不通过
  您的代码已保存
  运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。点击对比用例标准输出与你的输出
  case通过率为93.33%

  import java.util.*;
  public class Main
  {
    public static void main(String [] args)
    {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext())
        {
            String str=sc.next();
            int index=0;
            Stack<String> operStack=new Stack<>();//符号栈
            List<String> list=new LinkedList<>();//一开始是存放数的集合，到后来也会存放符号
            while(index<str.length())//扫描中缀表达式
            {
                String s=""+str.charAt(index);
                //如果扫描到的是符号
                if(s.matches("[^a-z]"))
                {
                    while(true)
                    {
                        //如果符号栈为空
                    if(operStack.empty())
                    {
                        operStack.push(s);//直接进入符号栈
                        break;
                    }
                    else if(getPriority(s)>getPriority(operStack.peek()))//如果运算符优先级比栈顶元素优先级高
                    {
                        operStack.push(s);
                        break;                    }
                    else//否则将栈顶元素弹出来，放到list集合中
                    {
                        list.add(operStack.pop());
                        //再次与新的栈顶元素进行比较运算符优先级
                    }
                    }                  
                }
  
                else if(s.matches("[a-z]"))//如果扫描到的是数
                {
                    String builder="";
                    while(index<str.length()&&(""+str.charAt(index)).matches("[a-z]"))
                    {
                        builder+=(""+str.charAt(index)); 
                        index++;
                    }
                    list.add(builder);
                    builder="";
                    index-=1;
  
                }
  
                index++;
            }
  
            while(!operStack.empty())
            {
                list.add(operStack.pop());
            }
  
            for(String item:list)
            {
                System.out.print(item);
            }
        }
    }
  
    private static int getPriority(String oper)//获取运算符的优先级
    {
        if(oper.equals("+")||oper.equals("-"))
        {
            return 1;
        }
        else if(oper.equals("*")||oper.equals("/"))
        {
            return 2;
        }
        else
        {
            System.out.println("非法运算符！");
            return 0;
        }
  
    }
  }

string = input()

def cmp(a, b):
    if (a == "-" or a == "+") and (b == "*" or b == "/"):
        return True
    else:
        return False

opts, stack = [], []
i = 0
while i < len(string):
    c = string[i]
    if c.isalpha():
        stack.append(c)
    else:
        while opts and not cmp(opts[-1], c):
            stack.append(opts.pop())
        opts.append(c)
    i += 1
while opts:
    stack.append(opts.pop())
print("".join(stack))