上期回顾

我们上期学习由中缀表达式转为后缀表达式 但是没有进行计算。这一期我们进行后缀表达式计算讲解。

由中缀表达式转化为后缀表达式我们还是得到一个以空格分隔好的字符串。我们现在考虑的是计算问题。所以其实大体思路和中缀表达式计算基本相似。下面是我对其进行分析实现。

思路分析

首先 我们由上期文章学会了把一个中缀表达式转化为后缀表达式了，可是得到的式子却和中缀表达式不完全相同(格式上)。我们得到的后缀表达式只有数字和操作符 而且都是已经拿空格把他们分隔开了。所以现在我们只需要对其遍历进行计算。

定义一个字符串 我们还是拿老例子来说。通过调用我们学过的中缀转后缀表达式的类中转化的方法函数来进行直接转化。转化方法是用static进行修饰的，所以我们直接用类名点方法名直接调用，传入我们定义好的字符串，赋给新的字符串。这样我们的后缀表达式就产生了。

代码实现:

 String infixExpression = "(10+20/2*3)/2+8";
 String suffixExpression = InfixToSufix.infixToSuffix(infixExpression);

我们现在得到后缀表达式了 就是进行计算。在这里我们用到一个辅助栈用来存放数字就可以 因为操作符不需要进栈 直接在外进行使用即可。所以定义的stack就是Integer类型的。我们还是要用split()方法以空格分割字符串，放入字符串数组中，以便更好地去遍历。

现在对字符串数组进行遍历。首先要把空字符串滤除掉。然后再去进行判断是否为数字(还是定义一个函数方法isNumber)还是操作符;当遍历到数字的时候，直接让数字进栈即可（注意: 我们遍历到的数字是以字符串形式的格式遍历的，而我们进栈的是数字格式，所以在这里还得把字符串改为数字格式。new Integer(token) 方法有很多种）。如果遍历到操作符我们就直接进行计算操作(在定义一个函数方法 processAnOperator()传入栈和操作符两个参数)。最终我们会得到一个最终结果在栈顶 最后把栈顶数字弹出即是我们最终后缀表达式计算的结果。

代码实现

    private static int evaluateSuffix(String expression) {
        ArrayStack<Integer> stack = new ArrayStack<>();
        String[] tokens = expression.split(" ");
        for (String token : tokens){
            if (token.length() == 0){
                continue;
            }
            if (isNumber(token)){
                stack.push(new Integer((token)));
            }else {
                processAnOperator(stack,token);
            }

        }
        return stack.pop();
    }

上述提及到两个附加函数方法是isNumber()和processAnOperator();我们现在对齐进行讲解分析。

isNumber()方法是在遍历数组的时候判断是否为数字的，我们使用到maches("\\d+");这就是对其进行数字匹配我们在上期学习中也提及到。为了巩固知识 起到让我们牢记的作用。我们大概讲一下。里面参数是用 \ 来对 \d 进行转转义的，是判断数字的方法 如果数字和其他字符参杂就会报错以及至少要有一个数字即可。我们在这直接使用maches()返回true或者false即可。

    private static boolean isNumber(String token) {
        return token.matches("\\d+");
    }

processAnOperator()方法是我们计算的方法 传入两个参数是栈stac和遍历到的操作符token；

先把数字进栈 如果遇到操作符弹出两个数字进行计算，先弹出的放在后面，第二出来的放在前面进行计算。把计算结果在此进栈，不断的去遍历直到遍历完。最终计算完栈顶应该有一个最终结果。最后弹出即可。

   private static void processAnOperator(ArrayStack<Integer> stack, String token) {
        int num1 = stack.pop();
        int num2 = stack.pop();
        if (token.equals("+")){
            stack.push(num2+num1);
        }else if (token.equals("-")){
            stack.push(num2-num1);
        }else if (token.equals("*")){
            stack.push(num2*num1);
        }else if (token.equals("/")){
            stack.push(num2/num1);
        }
    }

所有代码思路我们都逐个进行了讲解 最终就可以得到后缀表达式的结果啦。我会不断的更新学习体会，与君共勉，请大家多关注关注。有问题可私信也可评论！谢谢各位读者的光临！

完整代码

package p2.线性结构;

import static jdk.nashorn.internal.runtime.JSType.isNumber;
//后缀表达式计算
//中缀表达式转为后缀表达式 最终得到  10 20 2 / 3 * + 2 / 8 +
public class SuffixCalculator {
    public static void main(String[] args) {
        String infixExpression = "(10+20/2*3)/2+8";
        String suffixExpression = InfixToSufix.infixToSuffix(infixExpression);
        int result = evaluateSuffix(suffixExpression);
        System.out.println(result);
    }

    private static int evaluateSuffix(String expression) {
        ArrayStack<Integer> stack = new ArrayStack<>();
        String[] tokens = expression.split(" ");
        for (String token : tokens){
            if (token.length() == 0){
                continue;
            }
            if (isNumber(token)){
                stack.push(new Integer((token)));
            }else {
                processAnOperator(stack,token);
            }

        }
        return stack.pop();
    }

    private static void processAnOperator(ArrayStack<Integer> stack, String token) {
        int num1 = stack.pop();
        int num2 = stack.pop();
        if (token.equals("+")){
            stack.push(num2+num1);
        }else if (token.equals("-")){
            stack.push(num2-num1);
        }else if (token.equals("*")){
            stack.push(num2*num1);
        }else if (token.equals("/")){
            stack.push(num2/num1);
        }
    }
    private static boolean isNumber(String token) {
        return token.matches("\\d+");
    }
}

运行结果

C++后缀表达式计算

继续上篇文章，实现计算器简单计算的功能

上篇文章C++中缀表达式转后缀表达式已经将中缀表达式转换成后缀表达式并保存在队列q中

后缀表达式算法思想：

1. 读取队列q顶端元素，并判断元素类型
   (1)若是数，将数压入运算栈sum中；
   (2)若是运算符，取出栈sum顶端的两个元素计算，结果压回栈sum;

2. 将队列顶端元素出栈，重复1操作，直至队列为空，此时sum中结果即为中缀表达式运算结果。

队列顶端元素对应类型值

代码

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

stack<char> s;//存放运算符的栈
queue<string> q;//输出队列（用于计算后缀表达式）
stack<double> sum;//用于计算后缀表达式
string str = "";//读取整个数字串并保存
int isp(char c)//栈内元素优先级判断
{
 switch (c)
 {
 case '#':
  return 0;
 case '(':
  return 1;
 case '+':
 case '-':
  return 3;
 case '*':
 case '/':
 case '%':
  return 5;
 case ')':
  return 6;
 }
}
int icp(char c)//栈外元素优先级判断
{
 switch (c) {
 case '#':
  return 0;
 case ')':
  return 1;
 case '+':
 case '-':
  return 2;
 case '*':
 case '/':
 case '%':
  return 4;
 case '(':
  return 6;
 }
}
void postfix(string input)//中缀表达式转后缀表达式代码
{
 s.push('#');//将#压入栈顶
 input += '#';//添加#号作为结束符
 for (int i = 0; i < input.length(); i++)
 {
  if ((input[i] >= '0' && input[i] <= '9') || input[i] == '.')
  {
   str += input[i];
  }
  else
  {
   if (str.length() > 0)//将数放入直接输出到队列中
   {
    q.push(str);
    str = "";
   }
   while (isp(s.top()) > icp(input[i]))
   {
    string a;//因为不能直接在栈和队列间转换字符和字符串类型，所以先将字符转成 字符串再出栈进队列
    a = s.top();
    q.push(a);
    s.pop();
   }
   //判断站外元素优先级决定元素是应该去除（=），还是进栈(<)
   if (isp(s.top()) == icp(input[i]))
   {
    s.pop();
   }
   else
   {
    s.push(input[i]);
   }
  }
 }
}

int wordType(string str)//队列顶元素类型
{
 if (str == "+")
 {
  return 1;
 }
 else if (str == "-")
 {
  return 2;
 }
 else if (str == "*")
 {
  return 3;
 }
 else if (str == "/")
 {
  return 4;
 }
 else {
  return 0;//元素数字
 }
}
void addOperation()//加运算，取运算栈的两个栈顶元素进行操作，结果压回运算栈
{
 double temp1, temp2,result;
 temp2 = sum.top();//先取操作数2(运算符后面的操作数)
 sum.pop();
 temp1 = sum.top();//再取操作数1(运算符前面的操作数)
 sum.pop();
 result = temp1 + temp2;
 sum.push(result);
}
void subOperation()//减运算
{
 double temp1, temp2, result;
 temp2 = sum.top();
 sum.pop();
 temp1 = sum.top();
 sum.pop();
 result = temp1 - temp2;
 sum.push(result);
}
void mulOperation()//乘运算
{
 double temp1, temp2, result;
 temp2 = sum.top();
 sum.pop();
 temp1 = sum.top();
 sum.pop();
 result = temp1 * temp2;
 sum.push(result);
}
void divOperation()//除运算
{
 double temp1, temp2, result;
 temp2 = sum.top();
 sum.pop();
 temp1 = sum.top();
 sum.pop();
 result = temp1 / temp2;
 sum.push(result);
}
void suffix()//计算后缀表达式，结果保留在栈sum中
{
 while (q.empty() == false)
 {
  int objType;//队列顶元素的类型（0:数字;1:+;2:-;3:*;4:/）
  objType = wordType(q.front());
  switch (objType)
  {
  case 0:
   sum.push(atof(q.front().c_str())); break;//使用c_str()方法将string转换成double型,将数字放入计算栈中
  case 1:
   addOperation(); break;
  case 2:
   subOperation(); break;
  case 3:
   mulOperation(); break;
  case 4:
   divOperation(); break;
  }
  q.pop(); //将队列顶元素出队列
 }
}

int main()
{
 string input;
 string och;
 cin >> input;
 postfix(input);
 //while (q.empty() == false)//队列不为空则输出队列元素
 //{
 // och = q.front();
 // cout << och;
 // q.pop();
 //}
 suffix();
 cout << sum.top() << endl;
}

实验结果

结果正确，自行验证。