算术表达式

     这几天学习《算法》这本书，第一章后面的习题，关于算术表达式，前序表达式，中序表达式，后序表达式的实现，我学习了两天，不断的编写调试，初步实现了具体功能。首先

     中序表达式是我们人类习惯使用的表达，但是，计算机很难使用。计算机一般是采用栈的技术来实现的，要么转换为前序表达式，要么转换为后序表达式。

     例如以后序表达式为例，12+34-56-**

     首先2与1+等于3，变成334-56-**

     然后4-3变成，3156-**

      然后6-5变成，311**

   然后1*1，变成31*

    最后等于3

  即从右至左取数，直到取出一个运算符，将刚取出的紧挨着运算符的两个操作数按运算符进行计算，结果回填至运算符。重复该步骤，直到最后只剩下一个字符串则剩下的字符串即为结果。
　　后序表达式的字符串扫描方式正好和前序相反，是从左往右扫描，规则类似。

中序表达式转后序表达式步骤

1、输入字符串，如“2*3/(2-1)+3*(4-1)”

2、从字符串中取出下一个字符

　　2.1.如果是操作数，则直接输出

　　2.2.如果是“（”，压入栈中

　　2.3.如果是运算符但不是“(”，“)”,则不断循环进行以下处理

　　　　2.3.1.如果栈为空，则此运算符进栈，结束此步骤

　　　　2.3.2.如果栈顶是“（”,则此运算符进栈，结束此步骤

　　　　2.3.2.如果此运算符与栈顶优先级相同或者更高，此运算符进栈，结束此步骤

　　　　2.3.4.否则，运算符连续出栈，直到满足上述三个条件之一，然后此运算符进栈

　　2.4、如果是“）”，则运算符连续出栈，直到遇见“（”为止,将“（”出栈且丢弃之

3、如果还有更多的字符串，则转到第2步

4、不在有未处理的字符串了，输出栈中剩余元素

程序源码为：

package sanzhang;
import ref.Stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class exe6 {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //String strold="2*3/(2-1)+3*(4-1)";
        String strold="((1+2)*((3-4)*(5-6)))";
        //String strold="(1+2)+(8/4)";
        //String strold="3*(2-1)*3*(6/3)";
        //存放栈
        Stack<String> oper=new Stack<String>();
         //转换成字符型数组
        char ch[]=strold.trim().toCharArray();
        //定义一个字符串数组
        String str[]=new String[ch.length];
        //存放结果数组
        List<String> list=new ArrayList<String>();
        //将原来表达式字符数组转换成字符串数组
         for(int i=0;i<ch.length;i++)
        {
            str[i]=String.valueOf(ch[i]);
        }
         //逐个判断字符串
        for(int i=0;i<str.length;i++)
        {
            //当输入的是操作数时，直接添加到结果表达式后
            if(str[i].matches("^[1-9]\\d*$"))//正则表达式
            {
                list.add(str[i]);
            }
            else
                //当输入的是左括号的时候，直接入栈
              if(str[i].equals("("))
              {
                  oper.push(str[i]);
              }
            //如果是右括号，则运算符连续出栈，直到遇见左括号为止，左括号出栈且丢弃它
              else
              if(str[i].equals(")"))
                {
                                 
                       while(oper.size()> 0 && !oper.peek().equals("("))
                       {
                           //运算符连续出栈
                           String ss = oper.pop();                     
                           list.add(ss);
                       }
                       //直到遇到左括号，并丢弃之
                       oper.pop();
                                            
                }
            //如果为操作符+-*/等
              else
              {
                  //如果栈为空，直接进栈
                  if(oper.isEmpty())
                  {
                      oper.push(str[i]);
                      continue;
                  }
                  else
                      //如果栈顶为左括号，运算符进栈
                  if(oper.peek().equals("("))
                  {
                      oper.push(str[i]);
                      continue;
                  }
                  else
                    //如果此运算符与栈顶优先级相同或更高，此运算符进栈，结束此步骤，取下一个字符，
                  if(priority(str[i])>priority(oper.peek()))
                  {
                                
                      oper.push(str[i]);
                  }
                  //如果三个条件均不满足，则连续出栈，直到满足其中三个一个，再进栈
                  else
                  {
                      do
                      {
                              
                          list.add(oper.pop());
                      }
                      while(!(oper.isEmpty()||oper.peek().equals("(")||priority(str[i])>priority(oper.peek())));
                      oper.push(str[i]);
                  }
              }
        }
        //如果此时栈非空，全部输出
        while(!oper.isEmpty())
        {
                
            list.add(oper.pop());
        }
        //对结果动态数组遍历
         for(int i=0;i<list.size();i++)
         {
             System.out.print(list.get(i)+"");
         }
         System.out.println();
         //输出计算结果
         System.out.println(calcauteAfterExpression(list));
    }
    // 返回运算符的优先级
        public static int priority(String temp)
        {
            char ch=temp.charAt(0);
            int pri;
            switch (ch)
            {
            case ‘+‘:
                pri = 1;
                break;
            case ‘-‘:
                pri = 1;
                break;
            case ‘*‘:
                pri = 2;
                break;
            case ‘/‘:
                pri = 2;
                break;
            default:
                pri = 0;
            break;
            }
            return pri;
        }
        //判断是否为运算符
        public static boolean IsOperator(String temp)
        {
                      
            if(temp.equals("+")||temp.equals("-")||temp.equals("*")||temp.equals("/"))
                return true;
            return false;
        }
          /// <summary>
        /// 计算后序表达式
        /// </summary>
        //将操作数动态数组作为参数进行传递
        public static int  calcauteAfterExpression(List<String> newExpression )
        {
           int result=0 ;
           if (newExpression.size() > 1)
            {
                int i = 0;
                for (i = 0; i < newExpression.size(); i++)
                {
                    //首先判断是否为运算符
                    if (IsOperator(newExpression.get(i)))
                    {
                        //取运算符左边与运算符次左边的进行运算
                        if (newExpression.get(i).equals("+"))
                        {
                            result =Integer.parseInt(newExpression.get(i-2))+Integer.parseInt(newExpression.get(i-1));
                        }
                        else if (newExpression.get(i).equals("-"))
                        {
                            result =Integer.parseInt(newExpression.get(i-2))-Integer.parseInt(newExpression.get(i-1));
                        }
                        else if (newExpression.get(i).equals("*"))
                        {
                            result =Integer.parseInt(newExpression.get(i-2))*Integer.parseInt(newExpression.get(i-1));
                        }
                        else if (newExpression.get(i).equals("/"))
                        {
                            result =Integer.parseInt(newExpression.get(i-2))/Integer.parseInt(newExpression.get(i-1));
                        }
                        break;
                    }
                }
                //第一轮计算完毕，将运算符所在的位置用计算得到的结果进行替换，并把运算符左边的元素和次左边的元素移除
                newExpression.set(i, String.valueOf(result));
                newExpression.remove(i-1);
                newExpression.remove(i-2);
                //再进行递归运算
                calcauteAfterExpression(newExpression);
            }
           //直到运算符全部用完，只剩下最后一个操作数，即为我们所需要的值
          return Integer.parseInt(newExpression.get(0));
        }
}

中序表达式转前序表达式步骤

1、反转输入字符串，如“2*3/(2-1)+3*(4-1)” 反转后为“ )1-4(*3+)1-2(/3*2”，

2、从字符串中取出下一个字符

　　2.1.如果是操作数，则直接输出

　　2.2.如果是“)”，压入栈中

　　2.3.如果是运算符但不是“(”，“)”,则不断循环进行以下处理

　　　　2.3.1.如果栈为空，则此运算符进栈，结束此步骤

　　　　2.3.2.如果栈顶是“)”,则此运算符进栈，结束此步骤

　　　　2.3.2.如果此运算符与栈顶优先级相同或者更高，此运算符进栈，结束此步骤

　　　　2.3.4.否则，运算符连续出栈，直到满足上述三个条件之一，然后此运算符进栈

　　2.4、如果是“(”，则运算符连续出栈，直到遇见“)”为止,将“)”出栈且丢弃之

3、如果还有更多的字符串，则转到第2步

4、不在有未处理的字符串了，输出栈中剩余元素

5、再次反转字符串得到最终结果

package sanzhang;
import java.util.*;
public class exe7 {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //String strold="2*3/(2-1)+3*(4-1)";
        String strold="((1+2)*((3-4)*(5-6)))";
        Stack<String> oper=new Stack<String>();
        StringBuffer sb=new StringBuffer();//记录结果表达式
        char ch[]=strold.trim().toCharArray();
        String str[]=new String[ch.length];
        List<String> list=new ArrayList<String>();
             
        for(int i=ch.length-1;i>=0;i--)
        {  
                list.add(String.valueOf(ch[i]));
        }
        //获得反转字符串
        for(int j=0;j<str.length;j++)
        {
            str[j]=list.get(j);
        }
              
        for(int i=0;i<str.length;i++)
        {
             //如果是操作数，直接输出
            if(str[i].matches("^[1-9]\\d*$"))
            {
                sb.append(str[i]);
            }
            //如果是“）”，压入栈中
            else
            if(str[i].equals(")"))
                    {
                       oper.push(str[i]);
                    }
            //如果是左括号，则运算符连续出栈，直到遇见右括号为止，右括号出栈且丢弃它
            else
            if(str[i].equals("("))
            {
                //右括号
                while (oper.size()> 0 && !oper.peek().equals(")"))
                {
                    String ss = oper.pop();                         
                    sb.append(ss);
                }
                //右括号出栈且丢弃它
               oper.pop();
            }
            else
            {
                 //如果栈为空，次运算符进栈，结束此步骤，取下一个字符
                if (oper.size()== 0)
                {
                         
                    oper.push(str[i]);
                }
                //如果栈顶是“）”，此运算符进栈，结束次步骤，读取下一个字符
                else if (oper.peek().toString() == ")")
                {
                    oper.push(str[i]);
                }
                //如果此运算符与栈顶优先级相同或更高，此运算符进栈，结束次步骤，取下一个字符，
                else if (priority(str[i])>=priority(oper.peek().toString()))
                {
                    oper.push(str[i]);
                        
                }
                //否则，运算符连续出栈，直至满足上述三个条件之一退出此步骤
                else
                {
                    do
                    {
                        String podstr = oper.pop().toString();                          
                        sb.append(podstr);
                    } while (!(oper.size() == 0 ||oper.peek().toString() == ")" ||
                        priority(str[i])>=priority(oper.peek().toString())));
                  oper.push(str[i]);
                         
                }
            }
                      
        }
            while(oper.size()!=0)
            {
                sb.append(oper.pop());
            }
                  
            System.out.println(sb.reverse());
    }
    // 返回运算符的优先级
    public static int priority(String temp)
    {
        char ch=temp.charAt(0);
        int pri;
        switch (ch)
        {
        case ‘+‘:
            pri = 1;
            break;
        case ‘-‘:
            pri = 1;
            break;
        case ‘*‘:
            pri = 2;
            break;
        case ‘/‘:
            pri = 2;
            break;
        default:
            pri = 0;
        break;
        }
        return pri;
    }
}

算术表达式,布布扣,bubuko.com

算术表达式

原文：http://liuzhangheng.blog.51cto.com/8792220/1392449