中缀表达式转后缀表达式

[编程题]中缀表达式转后缀表达式

热度指数：2108 时间限制：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/+

算法知识视频讲解

Java

LHC0512

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)

Java

肥咩咪

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

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

Java

Evacuation

用递归做，类似表达式求值

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)

Java

烟云20180822223767

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)