逆波兰计算器的实现

输入一个逆波兰表达式(后缀表达式), 使用栈(Stack), 计算其结果
支持小括号和多位数整数, 因为这里我们主要针对于数据结构, 因此计算器进行简化, 只支持对整数的计算
思路分析
代码完成

package com.beyond.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {

	public static void main(String[] args) {
		// 先定义一个逆波兰表达式
		// (3+4)*5-6  => 3 4 + 5 * 6 -
		// 为了方便, 逆波兰表达式 的数字和符号使用空格隔开
		String suffixExpression = "3 4 + 5 * 6 -";
		
		// 思路:
		// 1. 先将 "3 4 + 5 * 6 -" => 放到 ArrayList中
		// 2. 将 ArrayList 传递给一个方法, 遍历ArrayList 配合 栈 完成计算
		
		List<String> rpnList = getListString(suffixExpression);
		System.out.println(rpnList);
		System.out.println(calculate(rpnList));
	}

	
	// 将一个逆波兰表达式, 依次将数据和运算符 放入 ArrayList 中
	public static List<String> getListString(String suffixExpression){
		// 将suffixExpression 分割
		String split [] = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>();
		for(String ele: split) {
			list.add(ele);
		}
		return list;
	}
	
	// 完成对逆波兰表达式的运算
	/**
	 * 1. 从左到右扫描, 将3和4压入堆栈;
	 * 2. 遇到 ＋ 运算符, 因此弹出 4和3 (4 为栈顶元素,3为次栈顶元素), 计算 3+4 的值, 得7, 再将7 入栈
	 * 3. 将 5 入栈
	 * 4. 接下来是 * 运算符, 因此 弹出 5和7, 计算出 7*5 = 35, 将35 入栈
	 * 5. 将6入栈
	 * 6. 最后是 - 运算符, 计算出 35 -6 的值, 即29, 由此得出最终结果
	 */
	public static int calculate(List<String> ls) {
		// 创建个栈, 一个栈即可
		Stack<String> stack = new Stack<String>();
		// 遍历 ls
		for(String item: ls) {
			// 使用一个正则表达式来取出数
			if (item.matches("\\d+")) {  // 匹配的是多位数
				// 入栈
				stack.push(item);
			}else {
				// pop 出两个数, 并运算, 再入栈
				int num2 = Integer.parseInt(stack.pop());
				int num1 = Integer.parseInt(stack.pop());
				int res = 0; 
				if (item.equals("+")) {
					res = num1 + num2;
				}else if (item.equals("-")) {
					res = num1 - num2;
				}else if (item.equals("*")) {
					res = num1 * num2;
				}else if (item.equals("/")) {
					res = num1 / num2;
				}else {
					throw new RuntimeException("运算符有误!");
				}
				
				// 把 res 入栈
				stack.push(String.valueOf(res)); // 转成字符串, 还可以 Integer.toString(res) 或者使用 +""
				
			}
		}
	
		// 最后留在 stack 中的数据就是运算结果
		return Integer.parseInt(stack.pop());
		
	}
	
	
}

直接上代码



package cn.john.cal;

/**
 * 
 * @ClassName: Operators
 * 
 * @Description: 操作符枚举
 * 
 * @author: John
 * 
 * @date: 2017年5月9日 下午22:05:16
 * 
 * 
 */
public enum OperatorsEnum {

    PLUS(0, '+'), MINUS(0, '-'), MULTIPLY(1, '*'), DIVIDE(1, '/'), MODULAR(1, '%'), LEFT_BRACKET(2,
            '('), RIGHT_BRACKET(2, ')');

    public Integer prior;// 优先级
    public Character operator;// 操作符

    private OperatorsEnum(int prior, char operator) {
        this.prior = prior;
        this.operator = operator;
    }

    public String toString() {
        return String.valueOf(operator);
    }

}



package cn.john.cal;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * 
 * @ClassName: Cal
 * 
 * @Description:
 *               <p>
 *               基于后缀表达式的简易计算器，目前支持个位数加、减、乘、除、模和括号六种运算。
 *               <p>
 *               中缀表达式->后缀表达式 操作符入栈
 *               <p>
 *               后缀表达式->计算值 操作数入栈
 * 
 * @author: John
 * 
 * @date: 2017年5月9日 下午7:55:58
 * 
 */
public class Cal {

    /**

     * @Title: toPostFix

     * @Description: 将中缀表达式转换为后缀表达式

     * @param infix
     * @return

     * @return: String

     */
    public String toPostFix(String infix) {
        // 算式字符数组
        char[] ch = infix.trim().toCharArray();
        LinkedList<OperatorsEnum> stack = new LinkedList<OperatorsEnum>();
        StringBuilder sb = new StringBuilder();

        OperatorsEnum op = null;

        for (int i = 0; i < ch.length; i++) {
            // 对每个算式字符，检查它是不是操作符
            if ((op = isOperator(ch[i])) == null) {
                sb.append(ch[i]);
            } else {
                // 右括号
                // 持续弹出栈顶元素直到遇到左括号，但是不输出左括号
                if (op.equals(OperatorsEnum.RIGHT_BRACKET)) {
                    // 如果不是左括号，持续弹出并输出
                    while (!stack.peek().equals(OperatorsEnum.LEFT_BRACKET)) {
                        sb.append(stack.pop());
                    }
                    // 此时栈顶元素为左括号，直接弹出，不输出
                    stack.pop();
                } else {
                    // 非右括号
                    // 1、弹出并输出所有高优先级或者同等优先级，直到遇到低优先级或者左括号为止
                    // 上面的弹出语句有可能将栈弹空，检查stack的size避免NPE
                    while (stack.size() > 0 && stack.peek().prior >= op.prior
                            && !stack.peek().equals(OperatorsEnum.LEFT_BRACKET)) {
                        sb.append(stack.pop());
                    }
                    // 2、将当前操作符入栈
                    stack.push(op);
                }
            }
        }
        // 弹出所有栈中剩余操作符
        while (stack.size() > 0) {
            sb.append(stack.pop());
        }

        return sb.toString();
    }

    /**

     * @Title: calc

     * @Description: 计算后缀表达式的值

     * @param postfix
     * @return

     * @return: double

     */
    public double calc(String postfix) {
        char[] ch = postfix.toCharArray();
        LinkedList<Double> stack = new LinkedList<Double>();
        OperatorsEnum op = null;
        for (int i = 0; i < ch.length; i++) {
            if ((op = isOperator(ch[i])) == null) {
                // 不是操作符，将当前数值入栈
                stack.push(Double.parseDouble(String.valueOf(ch[i])));
            } else {
                // 是操作符，进行计算
                double b = stack.pop();
                double a = stack.pop();
                switch (op) {
                case PLUS:
                    stack.push(a + b);
                    break;
                case MINUS:
                    stack.push(a - b);
                    break;
                case MULTIPLY:
                    stack.push(a * b);
                    break;
                case DIVIDE:
                    stack.push(a / b);
                    break;
                case MODULAR:
                    stack.push(a % b);
                    break;
                default:
                    break;
                }
            }
        }
        return stack.pop();
    }

    /**

     * @Title: isOperator

     * @Description: 判断字符是否为操作符

     * @param ch
     * @return

     * @return: OperatorsEnum

     */
    private OperatorsEnum isOperator(char ch) {
        for (OperatorsEnum op : OperatorsEnum.values()) {
            if (ch == op.operator) {
                return op;
            }
        }
        return null;
    }


    // test

    /**

     * @Title: readEquation

     * @Description: 终端输入算式

     * @return

     * @return: String

     */
    public String readEquation() {
        Scanner sc = new Scanner(System.in);
        String equation = sc.nextLine();
        sc.close();
        return equation;
    }

    public static void main(String[] args) {
        Cal c = new Cal();
        System.out.println("Please input an equation,press ENTER to submit!");
        String infix = c.readEquation();
        String s = c.toPostFix(infix);
        System.out.println("postfix: " + s);
        System.out.println("Result: "+infix + "=" + c.calc(s));
    }
}

 解题思路

循环输入，获取逆波兰表达式（后缀表达式），然后进行以下步骤，直到测试完所有的测试用例：

遇到数字字符串，将该数字字符串转化为数字然后入栈。利用int atio(const char ptr）将数字类型的字符串转换成整形数据；它包含在stdlib.h头文件中；

	这里的参数类型是char所以这里要将string转化为c类型的string，在进行转化。
	
遇到操作符时，从栈顶取两个数字，然后进行该运算符所对应运算，完成好将结果入栈。
NOTE：根据逆波兰表达式定义：先取到的数字为运算符的右操作数。

继续1和2，直到处理完所有的字符串，最终栈顶元素即为所要结果。

代码

#include<iostream>
#include<stack>
#include<string>
#include<cstdlib>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        if(n<3 || n>50)
            return 0;
        
        stack<int> st;
        int num1=0;
        int num2=0;
        string str;
        
        for(int i=0;i<n;i++)
        {
            cin>>str;
            if((str[0]>='0') && (str[0]<='9'))
                st.push(atoi(str.c_str()));
            else
            {
                num1=st.top();
                st.pop();
                num2=st.top();
                st.pop();
                if(str=="+")
                {
                    num1=num2+num1;
                    st.push(num1);
                }
                else if(str=="-")
                {
                    num1=num2-num1;
                    st.push(num1);
                }
                 else if(str=="*")
                {
                    num1=num2*num1;
                    st.push(num1);
                }
                 else if(str=="/")
                {
                    num1=num2/num1;
                    st.push(num1);
                }
                
            }
        }
        cout<<st.top()<<endl;
    }
    
    return 0;
}



 

import java.util.Stack;

public class CalculateExpression {

    /**
     * 中缀表达式转后缀表达式，需要借助栈来存放操作符
     * <p>
     * 1. 遇到的是数字，直接输出
     * 2. 遇到的第一个操作符进栈
     * 3. 遇到"("进栈
     * 4. 遇到其他操作符oper：栈一直弹出，直到栈顶为优级低于oper的操作符或"("为止，然后oper进栈
     * 5. 遇到")"，将第一个"("之前的全部弹出
     * 6. 最后将栈中剩下的操作符全部弹出
     */
    public static String toPostFix(String expStr) {

        StringBuilder postFix = new StringBuilder();//后缀表达式

        Stack<String> stack = new Stack<String>();//存放运算符的栈

        for (int i = 0; i < expStr.length(); i++) {
            char element = expStr.charAt(i);
            switch (element) {
                case '+':
                case '-':
                    //不是空、不是(
                    while (!stack.isEmpty() && !stack.peek().equals("(")) {//弹出元素，直到遇到优先级更低，或者栈为空（"("只会遇到")"弹出），故+、-一直弹出直到"("或者为空
                        postFix.append(stack.pop() + " ");
                    }
                    stack.push(String.valueOf(element));
                    break;
                case '*':
                case '/':
                    while (!stack.isEmpty() && !stack.peek().equals("(") && !stack.peek().equals("+") && !stack.peek().equals("-")) {//不是+、-、(、不是空，或者不为空、（是* 或 是/）
                        postFix.append(stack.pop() + " ");
                    }
                    stack.push(String.valueOf(element));
                    break;
                case '(':
                    stack.push(String.valueOf(element));
                    break;
                case ')':
                    String out = stack.pop();
                    while (!out.equals("(")) {
                        postFix.append(out + " ");
                        out = stack.pop();
                    }
                    break;
                //数字，直接拿出
                default:
                    if (element >= '0' && element <= '9') {
                        postFix.append(element + " ");
                    }
                    break;
            }
        }
        //最后把所以运算符出栈
        while (!stack.isEmpty()) {
            postFix.append(stack.pop() + " ");
        }
        return postFix.toString();
    }


    /**
     * 后缀表达式计算（用栈来存操作数）
     * <p>
     * 1. 遇到操作数，进栈
     * 2. 遇到操作符，从栈中弹两个出来计算（后取的减先取的）
     * 3. 将计算后的操作数进栈
     * <p>
     * 重复直到操作符计算完，最终栈的元素为结果
     */
    public static int calculatePostFixValue(String postFix) {
        Stack<Integer> stack = new Stack<>();
        //栈用于存储操作数，协助计算
        for (int i = 0; i < postFix.length(); i++) {
            char ch = postFix.charAt(i);
            switch (ch) {
                case '+':
                    stack.push(stack.pop() + stack.pop());
                    break;
                case '-':
                    int p1 = stack.pop();
                    int p2 = stack.pop();
                    stack.push(p2 - p1);
                    break;
                case '*':
                    stack.push(stack.pop() * stack.pop());
                    break;
                case '/':
                    int p3 = stack.pop();
                    int p4 = stack.pop();
                    stack.push(p4 / p3);
                    break;
                case ' '://case ' '不处理
                    break;
                default://数字
                    stack.push(Integer.parseInt(String.valueOf(ch)));
            }
        }
        return stack.pop();
    }


    public static int calculate(String expStr) {
        String postFix = toPostFix(expStr);
        return calculatePostFixValue(postFix);
    }

    public static void main(String[] args) {
        System.out.println(calculate("4*(2+3)-7*2"));//6
        System.out.println(calculate("(3+2)/(4-2)"));//2
    }
}