首页 > 试题广场 >

中缀表达式转后缀表达式

[编程题]中缀表达式转后缀表达式
  • 热度指数:2097 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
将中缀表达式转为后缀表达式,输入 a+b*c/d-a+f/b 输出 abc*d/+a-fb/+
要求:语言不限;输入输出均为单个字符串;操作数用单个小写字母表示,操作符只需支持 +-*/,按照四则运算顺序确定优先级,不包含括号

输入描述:
一个字符串为合法的中缀表达式
字符串长度不超过200000


输出描述:
对应的后缀表达式
示例1

输入

a+b*c/d-a+f/b

输出

abc*d/+a-fb/+

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

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))
发表于 2019-08-29 18:03:46 回复(0)
常规方法,用栈将中缀表达式转化成后缀表达式。
准备一个符号栈和一个字符数组,然后遍历表达式中的字符:
(1) 由于后缀表达式是数字在前,运算符在后,如果遇到数字字符,直接追加到字符数组。
(2) 如果遇到运算符,我们先要检查一下符号栈是否为空,为空就直接将运算符压入到符号栈。由于符号栈的栈顶是我们马上要进行的运算,因此要保证栈顶运算的优先级最高。如果栈顶不为空,我们就需要比较一下当前运算符和栈顶运算符的优先级,如果当前运算符的优先级大,直接入栈,栈顶运算符的优先级仍然保持最高;如果当前运算符的优先级更小,说明栈顶的运算符需要紧接在某些数字的后面了,这些数字需要先进行运算,一直弹栈追加运算符到字符数组中,直到栈顶的优先级小于当前运算符的优先级(等于也要弹栈,因为同级运算符要保证从左往右的运算顺序),然后当前运算符入符号栈。
遍历完成后可能符号栈中还存在运算符,全部弹出追加到字符数组中即可,这样字符数组中的字符顺序就构成了后缀表达式。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String expr = br.readLine().trim();
        HashMap<Character, Integer> priority = new HashMap<>();    // 存放运算符的优先级
        priority.put('+', 0);
        priority.put('-', 0);
        priority.put('*', 1);
        priority.put('/', 1);
        Stack<Character> sign = new Stack<>();
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < expr.length(); i++){
            char c = expr.charAt(i);
            if(c == '+' || c == '-' || c == '*' || c == '/'){     // 运算符号
                while(!sign.isEmpty() && priority.get(sign.peek()) >= priority.get(c))
                    res.append(sign.pop());      // 保持符号栈的栈顶优先级最高
                sign.add(c);
            }else
                res.append(c);     // 如果是数字直接入list
        }
        while(!sign.isEmpty()) res.append(sign.pop());
        System.out.println(res);
    }
}

编辑于 2021-04-13 13:46:22 回复(0)
用递归做,类似表达式求值
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * created by srdczk 2019/9/21
 */
public class Main {
    private static char[] chs;
    private static int i = 0;
    private static String exp() {
        StringBuilder sb = new StringBuilder();
        sb.append(term());
        while (i < chs.length) {
            if (chs[i] == '+' || chs[i] == '-') {
                char c = chs[i++];
                sb.append(term());
                sb.append(c);
            } else break;
        }
        return sb.toString();
    }

    private static String term() {
        StringBuilder sb = new StringBuilder();
        sb.append(num());
        while (i < chs.length) {
            if (chs[i] == '*' || chs[i] == '/') {
                char c = chs[i++];
                sb.append(num());
                sb.append(c);
            } else break;
        }
        return sb.toString();
    }

    private static String num() {
        return String.valueOf(chs[i++]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        chs = bf.readLine().toCharArray();
        System.out.println(exp());
    }
}


发表于 2019-09-21 10:53:00 回复(0)
#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;
}


发表于 2019-08-22 13:10:18 回复(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])

发表于 2019-07-17 17:34:37 回复(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;
}

发表于 2019-07-10 20:14:57 回复(1)
#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;
}

发表于 2019-11-25 12:54:48 回复(0)
Java解法
import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        char[] array = scanner.nextLine().toCharArray();
        StringBuilder builder = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        map.put('/',2);
        for (char c : array) {
            if (Character.isLetter(c)) builder.append(c);
            else {
                while (!stack.isEmpty()&&map.get(c)<=map.get(stack.peek())){
                    builder.append(stack.pop());
                }
                stack.push(c);
            }
        }
        while (!stack.empty()) builder.append(stack.pop());
        System.out.println(builder.toString());
    }
}


发表于 2020-03-06 10:06:08 回复(0)
#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;
}

发表于 2022-12-03 17:02:44 回复(0)
自己用学的模板和栈,c++写的,很长,还有待改进:
#include <iostream>
#include <string>
using namespace std;
//const int Max = 200000;
const int Max = 200;

template<class T>
class Sqlink {
private:
	T top;
	T* data;
public:
	Sqlink() {
		top = -1;
		data = new T[Max];
	}
	bool empty() {
		return top == -1;
	}
	bool push(T t) {
		if (top == Max - 1)
			return false;
		top++;
		data[top] = t;
		return true;
	}
	bool pop(T& t) {
		if (empty())
			return false;
		t = data[top];
		--top;
		return true;
	}
	bool getpop(T& t) {
		if (empty())
			return false;
		t = data[top];
		return true;
	}
	bool myoperation(char m, char n) {
		if ((m == '*' || m == '/') && (n == '+' || n == '-'))
			return false;
		else
			return true;
	}
	void mycout(string sum) {
		T n;                           
		for (int i = 0; i < sum.size(); ++i) {
			if (sum[i] == '*' || sum[i] == '/' || sum[i] == '+' || sum[i] == '-') {
				if (getpop(n)) {
					for (; myoperation(sum[i],n); getpop(n)) {
						pop(n);
						cout << n;
						if (empty())
							break;
					}
					push(sum[i]);
				}
				else {
					push(sum[i]);
				}
			}
			else {
				cout << sum[i];
			}
		}
		while (top != -1) {
			pop(n);
			cout << n;
		}
	}
};

int main() {
	string sum;
	cin >> sum;
	Sqlink<char> pmc;
	pmc.mycout(sum);
	return 0;
}



发表于 2022-09-25 21:39:53 回复(0)
#include <iostream>
#include<vector>
#include<string>
#include<map>
#include<stack>


using namespace std;

int main()
{
    map<char, int> priorityMap = {
        {'+',1},
        {'-',1},
        {'*',2},
        {'/',2},
        {'^',4}
    };
    std::string input;
    cin >> input;
    vector<char> array;
    for (int i = 0; i < input.length(); ++i)
    {
        array.push_back(input[i]);
    }

    string outPut;
    stack<int> symbol;
    for (int i = 0; i < array.size(); ++i)
    {
        // 处理为括号的情况,当遇到下一个右括号的时候,栈内必有元素一定与之对应
        if (array[i] == '[' || array[i] == '{' || array[i] == '(')
        {
            symbol.push(array[i]);
            continue;
        }

        // 将括号之上的符号全部弹出到输出中
        if (array[i] == ']' || array[i] == '}' || array[i] == ')')
        {
            while (symbol.top() != '[' && symbol.top() != '{' && symbol.top() != '(')
            {
                outPut += symbol.top();
                symbol.pop();
            }
            symbol.pop();// 弹出左括号
            continue;
        }

        // 若在优先级map里没找到key,则为数值类型,放入输出中
        if (priorityMap.find(array[i]) == priorityMap.end())
        {
            outPut += array[i];
        }
        else if (symbol.empty())
        {
            symbol.push(array[i]);
        }
        else
        {
            // 在这里面比较符号的优先级
            //遇到更高优先级符号,则放入符号栈中
            if (priorityMap[symbol.top()] < priorityMap[array[i]])
            {
                symbol.push(array[i]);
            }
            else
            {
                while (!symbol.empty() && priorityMap[symbol.top()] >= priorityMap[array[i]])
                {
                    outPut += symbol.top();
                    symbol.pop();
                }
                symbol.push(array[i]);
            }

        }
    }
    // 现在将栈中符号弹出到输出
    while (!symbol.empty())
    {
        outPut += symbol.top();
        symbol.pop();
    }
    cout << outPut;
    return 0;
}
发表于 2021-08-07 19:01:33 回复(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;
}

发表于 2020-12-18 16:05:38 回复(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(''))

发表于 2020-03-31 22:47:56 回复(0)
//关键是构造一个运算符的优先级函数
#include<iostream>
(720)#include<string>
#include<stack>
using namespace std;
//运算符优先级
int f(char c){
    int n=0;
    switch(c){
        case '*':n=2;break;
        case '/':n=2;break;
        case '+':n=1;break;
        case '-':n=1;break;
    }
    return n;
}
int main(){
    string s;
    getline(cin,s);
    stack<char>sta;
    string res="";
    for(int i=0;i<s.size();i++){
        if(s[i]<='z'&&s[i]>='a'){
            res+=s[i];
        }else{
            if(sta.empty()||f(sta.top())<f(s[i]))sta.push(s[i]);
            else if(f(sta.top())==f(s[i])){
                res+=sta.top();
                sta.pop();
                sta.push(s[i]);
            }
            else if(f(sta.top())>f(s[i])){
                while(!sta.empty()){
                    res+=sta.top();
                    sta.pop();
                }
                sta.push(s[i]);
            }
        }
    }
    while(!sta.empty()){
        res+=sta.top();
        sta.pop();
    }
    cout<<res;
    return 0;
}


发表于 2020-03-03 23:03:04 回复(0)
  • 第一次遇到时间复杂度过大不通过的问题,求分析

  • 不通过
    您的代码已保存
    运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。点击对比用例标准输出与你的输出
    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;
          }
    
      }
    }
发表于 2020-02-16 14:43:26 回复(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))

发表于 2019-09-04 03:15:56 回复(0)
Scanner sc = new Scanner(System.in);
char [] middle =sc.next().toCharArray();// 中缀字符数组
Stack<Character> result =new Stack<>();
Stack<Character> operator =new Stack<>();

for (int i = 0; i < middle.length; i++) {
if(middle[i]!='+' && middle[i]!='/'  && middle[i]!='*' &&middle[i]!='-'){
result.push(middle[i]);
int operlength =operator.size();
if(operlength>0){
if(i==middle.length-1){
for (int j = 0; j < operlength; j++) result.push(operator.pop());
}else{
for (int j = 0; j < operlength; j++) {
int pre = operator.peek() == '+' || operator.peek() == '-'?0:1;
int next = middle[i+1] == '+' || middle[i+1] == '-'?0:1;
if(pre>=next){
result.push(operator.pop());
}else{
break;
}
}
}

}
}else {
operator.push(middle[i]);
}
}
StringBuilder s=new StringBuilder();
result.stream().forEach(e->{
s.append(e);
});
System.out.println(s);
编辑于 2019-08-16 11:09:37 回复(0)
 后缀表达式是数字在前, 操作符在后, 所以需要用栈保存暂时还不计算的运算符. 同时括号和其他运算符区分开来, 只有是左括号就进栈, 右括号就出栈. 其他运算符比较优先级就可以了. 乘法和除法的优先级较高的理解是中缀表达式中需要先算, 只要遇到低级的运算符就表示在同一层面的运算中要计算了乘法或者除法了. 
发表于 2019-06-29 20:23:32 回复(0)
if __name__=='__main__':
    try:
        while True:
            s = input().strip()
            if s == '':
                break
            else:
                s = list(s)
                s_num = [s[0], ]
                s_p = []
                for i in range(0, len(s) - 1, 2):
                    if s[i + 1] in ['+', '-']:
                        s_num.append(s[i + 2])
                        s_p.append(s[i + 1])
                    else:
                        s_num[-1] = s_num[-1] + s[i + 2] + s[i + 1]
                r = [s_num[0], ]
                for j in range(len(s_p)):
                    r.append(s_num[j + 1])
                    r.append(s_p[j])
                print(''.join(r))
    except:
        pass

发表于 2019-04-19 21:55:21 回复(0)