数据结构之计算器的实现(JAVA)(四)

   原理:

       1.将中序表达式变化后续表达式

       2.当前字符为数字,将该数字放入栈中

       3.当前字符为操作符,从栈中取出两个树,根据操作符来运算,将运算结果放入到栈中

       4.重复,直到将字符操作完,此时栈中只剩下一个元素,即要运算的结果

   PS:我没有处理,只可以运行10以内的运算,如果有需要可以扩展
      

package com.lip.datastructure.tree;

import java.util.Iterator;
import java.util.Stack;

public class Calculator
	{

		public static void main(String[] args)
			{
				String obj = "a*(b+c)+c/d";
				String obj1 = "2*(1+3)+9/3";
				
				System.out.println(obj1+"="+calculator(obj1));

			}
		//利用后序表达式计算
		///原理:1.当期字符为字母或者数字,则直接入栈
		//      2.当前字符为操作符则从栈中取出两个数字计算
		//      3.将计算结果再放入到栈中,栈中最后剩余的一个元素就是要求的结果
		public static int calculator(String obj)
		{
			String postObj=tranform(obj);
			System.out.println();
			Stack<Integer>stack=new Stack<Integer>();
			for(int i=0;i<postObj.length();i++)
				{
					char ch=postObj.charAt(i);
					if(Character.isLetterOrDigit(ch))//字符或者数字
						{
							stack.push(Integer.parseInt(ch+""));
						}
					else//操作符
						{
							//取出两个数
							int op1,op2;
							op1=stack.pop();
							op2=stack.pop();
							switch (ch)
								{
								case '+':
									stack.push(op2+op1);
									break;
								case '-':
									stack.push(op2-op1);
									break;
								case '*':
									stack.push(op2*op1);
									break;
								case '/':
									stack.push(op2/op1);
									break;
								default:
									break;
								}
						}
				}
			return stack.pop();
		}
		// 中序遍历改为后续遍历
		public static String tranform(String obj)
			{
				Stack<Character> stack = new Stack<Character>();
				String obj2 = "";
				for (int i = 0; i < obj.length(); i++)
					{
						char ch = obj.charAt(i);
						if (Character.isLetterOrDigit(ch))// 字母或数字直接输出
							{
								obj2 += ch;
								System.out.print(ch);
							} else if (ch == ')')// 在栈中一致匹配到)操作符才停止出栈
							{
								char temp;
								while ((temp = stack.pop()) != '(')
									{
										obj2 += temp;
										System.out.print(temp);
									}
							} else
							// 比较操作符的进栈优先级
							{
								if (stack.isEmpty())
									{
										stack.push(ch);
										continue;
									}
								char temp = stack.peek();
								while (icp(ch) <= isp(temp))// 进栈优先级小于栈内优先级,则一直出栈
									{
										System.out.print(temp);
										obj2 += temp;
										stack.pop();
										if (stack.isEmpty())
											break;
										temp = stack.peek();
									}
								stack.push(ch);
							}
					}
				// 将栈中剩余的元素弹出来
				while (!stack.isEmpty())
					{
						char temp = stack.pop();
						obj2 += temp;
						System.out.print(temp);
					}
				return obj2;
			}
		// 操作符在栈内的优先级
				private static int isp(char ch)
					{
						switch (ch)
							{
							case '+':
							case '-':
								return 2;
							case '*':
							case '/':
								return 4;
							case ')':
								return 7;
							case '(':
								return 1;
							default:
								break;
							}
						return 0;
					}

				// 操作符进栈的优先级优先级
				private static int icp(char ch)
					{
						switch (ch)
							{
							case '+':
							case '-':
								return 3;
							case '*':
							case '/':
								return 5;
							case ')':
								return 1;
							case '(':
								return 7;
							default:
								break;
							}
						return 0;
					}

	}

技术分享

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。