The algebraic expressions are used daily are expressed as central elements (infix). This demonstration is understandable to humans because most operators (+, -, *, /) are binary operators and their division between the two operands together. However for PC, to calculate the value of an algebraic expression of this type is not as simple as we still do. To fix that, computer to transfer the representation of algebraic expressions from the elements into a different type of prefix or suffix.

What is the prefix expression, infix and suffix

In the introductory paragraph above as you might imagine how the infix expression, which is simply the operator will be placed between two operands, This course is the double star. So based on the position of the operator, whether we can perform algebraic expressions as other? The answer is, and as mentioned, As we have three expressions prefix (prefix), infix (infix) and suffixes (postfix). Let's look a little introduction on how to perform expression prefix and suffix to better understand them.

– Prefix: The expression prefix is ​​represented by the operator set up before the operand. This demonstration is also known under the name "Polish notation" by Polish mathematician Jan Łukasiewicz invented in 1920. With this representation, instead write x y as secondary form factor, I will write xy. Depending on the priority of operators that they will be different arrangements, You can see some examples in the following sections of this introduction.

– Postfix: In contrast with the prefix, ie, the operator will be placed after the operands. This demonstration called "reverse Polish notation" or abbreviated as RPN (Reverse Polish notation), was invented in the mid-decade 1950 by a philosopher and computer scientist Charles Hamblin Australian.

Một số ví dụ:

Method transfer from infix expression to postfix

Priority of operators

One of the important things before starting the calculation must be the priority of the operators in the expression into. For simplicity we consider only binary operators and usually include: multiply (+),subtract (-), multiply (*), divide (/). According to the operator "*, /"Has the higher priority and the two operators" , -". Thus we have taken priority modes as follows operator:

public int priority(char c){		// thiet lap thu tu uu tien
		if (c == '+' || c == '-') return 1;
		else if (c == '*' || c == '/') return 2;
		else return 0;
	}

Check operator and operand

In this transformation algorithm we need a method to check whether a component of the string is not the operator or operand. Instead of using the structure or switch if lengthy and inconvenient when developing, I will use Regex to check.
Also because the input string is an algebraic expression, Should operands would consider not only the number but also letters from az and AZ.
There is one rule is that when using only letters allowed only one letter represents an operand, even when using multiple digits may be combined into one digit operands.

public boolean isOperator(char c){ 	// kiem tra xem co phai toan tu
		char operator[] = { '+', '-', '*', '/', ')', '(' };
		Arrays.sort(operator);
		if (Arrays.binarySearch(operator, c) > -1)
			return true;
		else return false;
	}

Standardize Infix expression before converting

The expression can Infix entering excess whitespace, characters inappropriate or misspelled syntax.
This section of your view normalized string in Java

Also you have to merge adjacent digits of the number (operand), separation of the operator, separated from each other by a space. These elements I would call a token.

public String[] processString(String sMath){ // xu ly bieu thuc nhap vao thanh cac phan tu
		String s1 = "", elementMath[] = null;
		InfixToPostfix  IFP = new InfixToPostfix();
		sMath = sMath.trim();
		sMath = sMath.replaceAll("\\s+"," "); //	chuan hoa sMath
		for (int i=0; i<sMath.length(); i++){
			char c = sMath.charAt(i);//sMath.substring(i,1);
			if (!IFP.isOperator(c))
				s1 = s1 + c;
			else s1 = s1 + " " + c + " ";
		}
		s1 = s1.trim();
		s1 = s1.replaceAll("\\s+"," "); //	chuan hoa s1
		elementMath = s1.split(" "); //tach s1 thanh cac phan tu
		//System.out.println(s1);
		return elementMath;
	}

The algorithm to convert an Infix expression to seasoned Prefix:

Read each token in infix expression from left to right, with each token we perform the following steps:
– If the operand: for the output.
– If the opening parenthesis "(": entered stack
– If the closing parenthesis ")": operators take out and put in the stack output until you reach the opening parenthesis "(". (Parenthesis must be taken out of the stack)
– If the operator:
+/As long at the top of the stack is the operator and the operator precedence which equals or exceeds the current operator, the operator took it out of the stack and the output.
+/Putting the current operator on stack
After reviewing all infix expression, if the stack was then grab the token element in that place and to turn on output.

CEO: We will transfer the expression A * B C *((D-E)+F)/G from Infix form into a Postfix:

Install Java

public String[] postfix(String[] elementMath){
		InfixToPostfix  IFP = new InfixToPostfix();
		String s1 = "", E[];
		Stack <String> S = new Stack <String>();
		for (int i=0; i<elementMath.length; i++){ 	// duyet cac phan tu
			char c = elementMath[i].charAt(0);	// c la ky tu dau tien cua moi phan tu

			if (!IFP.isOperator(c)) 		// neu c khong la toan tu
				s1 = s1 + " " + elementMath[i];		// xuat elem vao s1
			else{						// c la toan tu
				if (c == '(') S.push(elementMath[i]);	// c la "(" -> day phan tu vao Stack
				else{
					if (c == ')'){			// c la ")"
						char c1;		//duyet lai cac phan tu trong Stack
						do{
							c1 = S.peek().charAt(0);	// c1 la ky tu dau tien cua phan tu
							if (c1 != '(') s1 = s1 + " " + S.peek(); 	// trong khi c1 != "("
							S.pop();
						}while (c1 != '(');
					}
					else{
						while (!S.isEmpty() && IFP.priority(S.peek().charAt(0)) >= IFP.priority(c)){
						// Stack khong rong va trong khi phan tu trong Stack co do uu tien >= phan tu hien tai
							s1 = s1 + " " + S.peek();	// xuat phan tu trong Stack ra s1
							S.pop();
						}
						S.push(elementMath[i]); // 	dua phan tu hien tai vao Stack
					}
				}
			}
		}
		while (!S.isEmpty()){	// Neu Stack con phan tu thi day het vao s1
			s1 = s1 + " " + S.peek();
			S.pop();
		}
		E = s1.split(" ");	//	tach s1 thanh cac phan tu
		return E;
	}

And finally the main program:

public static void main(String[] agrs){
		String sMath, elementMath[] = null;
		InfixToPostfix  IFP = new InfixToPostfix();
		Scanner input = new Scanner(System.in);
		sMath = input.nextLine();					// 	nhap bieu thuc
		elementMath = IFP.processString(sMath);		//	tach bieu thuc thanh cac phan tu
		elementMath = IFP.postfix(elementMath);		// 	dua cac phan tu ve dang postfix
		for (int i=0; i<elementMath.length; i++)	// 	xuat dang postfix
			System.out.print(elementMath[i] + " ");
		input.close();
	}

To test results are correct, you can use an online conversion service here . The website will also perform calculate the value of the expression after converting.

From here we can build a Calculate the value of the expression suffix