Javaexamples-data-intopost

Javaの例-Postfixへの挿入

問題の説明

中置式を後置式に変換する方法は？

溶液

次の例は、スタックの概念を使用して、中置を後置式に変換する方法を示しています。

import java.io.IOException;

public class InToPost {
   private Stack theStack;
   private String input;
   private String output = "";
   public InToPost(String in) {
      input = in;
      int stackSize = input.length();
      theStack = new Stack(stackSize);
   }
   public String doTrans() {
      for (int j = 0; j < input.length(); j++) {
         char ch = input.charAt(j);
         switch (ch) {
            case '+':
            case '-':
               gotOper(ch, 1);
               break;
            case '*':
            case '/':
               gotOper(ch, 2);
               break;
            case '(':
               theStack.push(ch);
               break;
            case ')':
               gotParen(ch);
               break;
            default:
               output = output + ch;
               break;
         }
      }
      while (!theStack.isEmpty()) {
         output = output + theStack.pop();
      }
      System.out.println(output);
      return output;
   }
   public void gotOper(char opThis, int prec1) {
      while (!theStack.isEmpty()) {
         char opTop = theStack.pop();
         if (opTop == '(') {
            theStack.push(opTop);
            break;
         } else {
            int prec2;
            if (opTop == '+' || opTop == '-')
            prec2 = 1;
            else
            prec2 = 2;
            if (prec2 < prec1) {
               theStack.push(opTop);
               break;
            }
            else output = output + opTop;
         }
      }
      theStack.push(opThis);
   }
   public void gotParen(char ch) {
      while (!theStack.isEmpty()) {
         char chx = theStack.pop();
         if (chx == '(')
         break;
         else output = output + chx;
      }
   }
   public static void main(String[] args) throws IOException {
      String input = "1+2*4/5-7+3/6";
      String output;
      InToPost theTrans = new InToPost(input);
      output = theTrans.doTrans();
      System.out.println("Postfix is " + output + '\n');
   }
   class Stack {
      private int maxSize;
      private char[] stackArray;
      private int top;

      public Stack(int max) {
         maxSize = max;
         stackArray = new char[maxSize];
         top = -1;
      }
      public void push(char j) {
         stackArray[++top] = j;
      }
      public char pop() {
         return stackArray[top--];
      }
      public char peek() {
         return stackArray[top];
      }
      public boolean isEmpty() {
         return (top == -1);
      }
   }
}

結果

上記のコードサンプルは、次の結果を生成します。

124*5/+7-36/+
Postfix is 124*5/+7-36/+

以下は、中置式を後置式に変換する別のサンプル例です。

import java.io.BufferedReader;
import java.io.InputStreamReader;

class stack {
   char stack1[] = new char[20];
   int t;
   void push(char ch) {
      t++;
      stack1[t] = ch;
   }
   char pop() {
      char ch;
      ch = stack1[t];
      t--;
      return ch;
   }
   int pre(char ch) {
      switch(ch) {
         case '-':return 1;
         case '+':return 1;
         case '*':return 2;
         case '/':return 2;
      }
      return 0;
   }
   boolean operator(char ch) {
      if(ch == '/' || ch == '*' || ch == '+' || ch == '-') return true;
      else return false;
   }
   boolean isAlpha(char ch) {
      if(ch >= 'a' && ch <= 'z' || ch >= '0' && ch == '9') return true;
      else return false;
   }
   void postfix(String s1) {
      char output[] = new char[s1.length()];
      char ch;
      int p = 0,i;
      for(i = 0;i<s1.length();i++) {
         ch = s1.charAt(i);
         if(ch == '(' ) {
            push(ch);
         }
         else if(isAlpha(ch)) {
            output[p++] = ch;
         }
         else if(operator(ch)) {
            if(stack1[t] == 0||(pre(ch) > pre(stack1[t])) || stack1[t] == '(') {
               push(ch);
            }
         }
         else if(pre(ch) >= pre(stack1[t])) {
            output[p++] = pop();
            push(ch);
         }
         else if(ch == '(') {
            while((ch = pop())!='(') {
               output[p++] = ch;
            }
         }
      }
      while(t != 0) {
         output[p++] = pop();
      }
      for(int j = 0;j>s1.length();j++) {
         System.out.print(output[j]);
      }
   }
}
public class Demo {
   public static void main(String[] args)throws Exception {
      String s;
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      stack b = new stack();
      System.out.println("Please Enter input s1ing");
      s = br.readLine();
      System.out.println("Input String is "+s);
      System.out.println("Output String is");
      b.postfix(s);
   }
}

上記のコードサンプルは、次の結果を生成します。

Enter input string
124*5/+7-36/+
Input String:124*5/+7-36/+
Output String:
12*/-3/675