欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

栈的应用(表达式求值)

程序员文章站 2022-06-03 15:51:45
...

栈的应用(表达式求值)

package cn.item.web.algorithm;
import java.util.Scanner;
import java.util.Stack;
public class Express {

    public static void main(String[] args) {
        Scanner  scanner = new Scanner(System.in);
        Stack<Integer> num = new Stack<Integer>();
        Stack<Character> opt = new Stack<Character>();
        String   string  = scanner.nextLine();
        char     []input = new  char[1000];
        input    =string.toCharArray();
        int n = 0;
        for (int i = 0; i < string.length(); i++)
        {
            char temp=input[i];
            if(Character.isDigit(input[i]))//数字  可能是多位数
            {
                n=n*10+Integer.parseInt(String.valueOf(input[i]));
            }
            else //字符
            {
                //首先将读取的数据放进num中
                if (n != 0)         //判断是不是0
                {
                    num.push(n);
                    n = 0;          // 归零,方便后续的计算
                }

                if (temp == '(')    // '('直接进opt
                {
                    opt.push(temp);
                }
                else if (temp ==')')    // ')' 需要找最近的 '(' 计算()之间数据
                {
                    while(opt.peek() != '(')
                    {
                        num.push(Cal(num.pop(),num.pop(),opt.pop()));  //opt取操作符,num取取数
                    }
                    opt.pop(); // C出栈
                }
                else if (compare(temp)>0) // 是运算字符
                {
                      if (opt.empty())    // 第一次加入
                      {
                          opt.push(temp);
                      }
                      else               //非第一次 //比较temp与当前opt栈顶大小
                      {
                          if (compare(temp)<=compare(opt.peek()))     //小于
                          {
                              num.push(Cal(num.pop(),num.pop(),opt.pop()));
                          }
                          opt.push(temp); //大于,进opt
                      }
                }

            }
        }

        if (n != 0)  //将最后一个数加入,如果是0就不加入
            num.push(n);
        while(!opt.empty())
        {
            num.push(Cal(num.pop(),num.pop(),opt.pop()));
        }
        System.out.println(num.pop());
    }

    public static int compare(Character c)
    {
        if (c == '+'||c == '-')
            return 1;
        else if (c == '*'||c == '/')
            return 2;
        else
            return 0;
    }
    public static int Cal(int a,int b,char c)
    {
        int sum = 0;
        if (c == '+')
            sum=a+b;
        else if (c == '-')
            sum=b-a;
        else if (c == '*')
            sum=a*b;
        else if (c == '/')
            sum=b/a;
        return sum;
    }
}

相关标签: 栈的应用