/**
 * rpn2value
 * 计算逆波兰式
 * @author   leo108 root@leo108.com
 */
function rpn2value($str){
    $arr = explode('','',$str);
    $stack = array();
    $len = count($arr);
    for($i=0;$i
<p>使用方法： </p><p>逆波兰式</p> 
<pre>$str = "1,2,3,+,*,4,-,5,+,7,*";
echo rpn2value($str);

/**
 * math_rpn
 *
 * 实现逆波兰式算法
 *
 * @author   sparkHuang 260558820@qq.com
 * @version  RPN 1.0.0
 *
 */
class math_rpn {
    //初始的计算表达式
    private $_expression = '''';
    //处理后的逆波兰表达式
    private $_rpnexp = array();
    //模拟栈结构的数组
    private $_stack  = array(''#'');
    //正则判断
    //private $_reg    = ''/^([A-Za-z0-9\(\)\+\-\*\/])*$/'';
    //优先级
    private $_priority = array(''#'' => 0, ''('' => 10, ''+'' => 20, ''-'' => 20, ''*'' => 30, ''/'' => 30);
    //四则运算
    private $_operator = array(''('', ''+'', ''-'', ''*'', ''/'', '')'');
    public function __construct($expression) {
        $this->_init($expression);
    }
    private function _init($expression) {
        $this->_expression = $expression;
    }
    public function exp2rpn() {
        $len = strlen($this->_expression);
        for($i = 0; $i _expression, $i, 1);
            if ($char == ''('') {
                $this->_stack[] = $char;
                continue;
            } else if ( ! in_array($char, $this->_operator)) {
                $this->_rpnexp[] = $char;
                continue;
            } else if ($char == '')'') {
                for($j = count($this->_stack); $j >= 0; $j--) {
                    $tmp = array_pop($this->_stack);
                    if ($tmp == "(") {
                        break;
                    } else {
                        $this->_rpnexp[] = $tmp;
                    }
                }
                continue;
            } else if ($this->_priority[$char] _priority[end($this->_stack)]) {
                $this->_rpnexp[] = array_pop($this->_stack);
                $this->_stack[]  = $char;
                continue;
            } else {
                $this->_stack[] = $char;
                continue;
            }
        }
        for($i = count($this->_stack); $i >= 0; $i--) {
            if (end($this->_stack) == ''#'') break;
            $this->_rpnexp[] = array_pop($this->_stack);
        }
        return $this->_rpnexp;
    }
}
//测试实例
$expression = "(A*(B+C)-E+F)*G";
var_dump($expression);
$mathrpn = new math_rpn($expression);
var_dump($mathrpn->exp2rpn());

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.regex.Pattern;

/**
 * 逆波兰整数计算器
 */
public class PolandNotation {
    public static boolean isNumber(String s){
        Pattern pattern = Pattern.compile("^[-+]?[.\\d]+$");
        return pattern.matcher(s).matches();
    }
    //中缀表达式转化为list
    public static List<String> toInfixList(String s){
        if (s==null) throw new RuntimeException("空表达式");
        if (String.valueOf(s.charAt(0)).equals(")")) throw new RuntimeException("错误的表达式");
        //\\s+匹配任何空白字符，包括空格、制表符、换页符等，等价[\f\n\r\t\v]
        s = s.replaceAll("\\s+","");
        System.out.println(s);
        List<String> list = new ArrayList<>();
        int i = 0;
        char c;
        String str = "";
        do {
            c = s.charAt(i);
            //不是数字并且不是.
            if (String.valueOf(c).matches("[\\D]")&&!String.valueOf(c).equals(".")){
                if (i==0&&(!String.valueOf(c).equals("("))){//第一个字符不是(拼接到str
                    str += c;
                }else if (i!=0&&String.valueOf(c).equals("-")&&String.valueOf(s.charAt(i-1)).equals("(")){//非第一个字符，根据前一个是否是(判断是负号还上减号
                    str += c;
                }else {
                    list.add(String.valueOf(c));
                }
                i++;
            }else {
                while (i<s.length()&&String.valueOf(c=s.charAt(i)).matches("[\\d.]")){//是符号或是小数点
                    str += c;
                    i++;
                }
                int a = str.indexOf(".");
                if (a!=-1){
                    if (str.indexOf(".",a+1)!=-1) throw new RuntimeException("数字中保含多个小数点");
                }
                if (!String.valueOf(str.charAt(0)).matches("[-\\d]")){
                    str = str.substring(1);
                }
                list.add(str);
                str = "";
            }
        }while (i<s.length());
        return list;
    }
    //中缀表达式列表改为后缀表达式列表
    public static List<String> parseSuffixList(List<String> list){
        Stack<String> s1 = new Stack<>();
        List<String> s2 = new Stack<>();
        for (String item:list) {
            if (isNumber(item)){
                s2.add(item);
            }else if (item.equals("(")){
                s1.push(item);
            }else if (item.equals(")")){//遇到)就将s1中的弹出加入s2，直到遇到s1的(
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();//弹出s1的(
            }else { //遇到符号了，看s1栈顶运算符，s1的优先级不小于它，就弹出放入s2，再与s1栈顶运算符比较，否则将这个符号放入s1
                while (s1.size()!=0&&(getValue(s1.peek())>=getValue(item))){
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        //将s1中剩下的运算符依次弹出到s2
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;
    }
    public static int getValue(String oper){
        if (oper.equals("*")||oper.equals("×")||oper.equals("/")){
            return 2;
        }else if (oper.equals("+")||oper.equals("-")){
            return 1;
        }else {
            return -1;
        }
    }
    public static String calculate(List<String> list){
        Stack<String> stack = new Stack<>();
        for (String item : list) {
            if (isNumber(item)){
                stack.push(item);
            }else {
                String s2 = stack.pop();
                String s1 = stack.pop();
                BigDecimal res = BigDecimal.ZERO;
                BigDecimal b2 = new BigDecimal(s2);
                BigDecimal b1 = new BigDecimal(s1);
                if (item.equals("+")){
                    res = b1.add(b2);
                }else if (item.equals("-")){
                    res = b1.subtract(b2);
                }else if (item.equals("*")||item.equals("×")){
                    res = b1.multiply(b2);
                }else if (item.equals("/")){
                    res = b1.divide(b2,BigDecimal.ROUND_HALF_UP);
                }else {
                    throw new RuntimeException("运算符错误");
                }
                stack.push(String.valueOf(res));
            }
        }
        return stack.pop();
    }
    public static void main(String[] args){
        List<String> strings = toInfixList("-1+((-30 .  1-   4)×5 /5+1)- 6");//[-1, +, (, (, -30.1, -, 4, ), ×, 5, /, 5, +, 1, ), -, 6]
        System.out.println("strings2.toString() = " + strings.toString());
        List<String> strings2 = parseSuffixList(strings);
        System.out.println("strings2.toString() = " + strings2.toString());//[-1, -30.1, 4, -, 5, ×, 5, /, 1, +, +, 6, -]
        String calculate = calculate(strings2);
        System.out.println(calculate);//-40.1
    }
}

目录

• 一.定义
• 二.逆波兰式的意义
• 三.逆波兰式的实现
• 1.方法
• 2.代码实现

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

string trans(string& s)
{
	string operand;
	stack<char> Operator;
	int flag = 0;//记录括号优先级
	for (const auto& e : s)
	{
		if (e == ''('')
		{
			Operator.push(e);
			flag = 1;
			continue;
		}
		if (e == '')'')
		{
			flag = 0;
			while (Operator.top() != ''('')
			{
				operand.push_back(Operator.top());
				Operator.pop();
			}
			Operator.pop();
			continue;
		}
		//操作符
		if (e == ''+'' || e == ''-'' || e == ''*'' || e == ''/'')
		{
			if (flag == 1)
			{
				if (Operator.top() == ''('')
				{
					Operator.push(e);

				}
				else if ((e == ''*'' || e == ''/'') && (Operator.top() == ''+'' || Operator.top() == ''-''))
				{
					Operator.push(e);
				}
				else//操作符的优先级低于或等于栈顶操作符则出栈，直至遇到''(''
				{
					while (Operator.top() != ''('')
					{
						operand.push_back(Operator.top());
						Operator.pop();
					}
					Operator.push(e);
				}
			}
			else if (Operator.empty())//栈空就入栈
			{
				Operator.push(e);
			}
			//操作符的优先级高于栈顶操作符，入栈
			else if ((e == ''*'' || e == ''/'') && (Operator.top() == ''+'' || Operator.top() == ''-''))
			{
				Operator.push(e);
			}
			else//操作符的优先级低于或等于栈顶操作符则出栈，直至栈空或者优先级高于栈顶操作符
			{
				while (!Operator.empty())
				{
					operand.push_back(Operator.top());
					Operator.pop();
				}
				Operator.push(e);
			}
		}
		//操作数
		else
		{
			operand.push_back(e);
		}
	}
	while (!Operator.empty())
	{
		operand.push_back(Operator.top());
		Operator.pop();
	}
	return operand;
}

int evalRPN(const string& s)
{
	stack<char> operand;
	int left = 0, right = 0;
	for (const auto& e : s)
	{
		if (e == ''+'' || e == ''-'' || e == ''*'' || e == ''/'')
		{
			switch (e)
			{
			case ''+'':
				right = operand.top();
				operand.pop();
				left = operand.top();
				operand.pop();
				operand.push(left + right);
				break;
			case ''-'':
				right = operand.top();
				operand.pop();
				left = operand.top();
				operand.pop();
				operand.push(left - right);
				break;
			case ''*'':
				right = operand.top();
				operand.pop();
				left = operand.top();
				operand.pop();
				operand.push(left * right);
				break;
			case ''/'':
				right = operand.top();
				operand.pop();
				left = operand.top();
				operand.pop();
				operand.push(left / right);
				break;
			}
		}
		else//操作数
		{
			operand.push(e - ''0'');
		}
	}
	return operand.top();
}

int RPN(const string& str)
{
	//1.中缀表达式转化为后缀表达式
	string s(str);
	s = trans(s);
	//2.后缀表达式计算答案
	return evalRPN(s);
}

int main()
{
	string s("1*(2*3+5)/5-4/2");
	int ret = RPN(s);
	cout << "ret:" << ret << endl;
	return 0;
}

• C++代码实现逆波兰式
• C++实现逆波兰式