C++后缀表达式计算
 
继续上篇文章，实现计算器简单计算的功能
 
上篇文章C++中缀表达式转后缀表达式已经将中缀表达式转换成后缀表达式并保存在队列q中
 
后缀表达式算法思想：
 
 
读取队列q顶端元素，并判断元素类型
 (1)若是数，将数压入运算栈sum中；
 (2)若是运算符，取出栈sum顶端的两个元素计算，结果压回栈sum;
 
 
将队列顶端元素出栈，重复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;
}
 
实验结果
 

 结果正确，自行验证。

问题描述
 　　输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。
 输入格式
 　　输入一行，包含一个表达式。
 输出格式
 　　输出这个表达式的值。
 样例输入
 1-2+3*(4-5)
 样例输出
 -4
 数据规模和约定
 　　表达式长度不超过100，表达式运算合法且运算过程都在int内进行。
 
package com.liuzhen.systemExe;


import java.util.Scanner;
import java.util.Stack;


public class Main{
    //计算表达式的值
    public void getExpressionValue(String A){
        char[] arrayA = A.toCharArray();
        Stack<Integer> Value = new Stack<Integer>();      //存放运算数字及表达式计算结果
        Stack<Character> Operator =  new Stack<Character>();   //存放运算符
        for(int i = 0;i < A.length();i++){
            int temp = 0;
            if(arrayA[i] >= '0' && arrayA[i] <= '9'){
                temp = arrayA[i] - '0';
                i = i + 1;
                while(i < A.length() && arrayA[i] >= '0' && arrayA[i] <= '9'){
                    temp = temp * 10 + (arrayA[i] - '0');
                    i++;
                }
                i--;     //对应上面一句i = i+1;因为在for循环中有i++自增操作，若不执行此句，会导致i自增两次
                Value.push(temp);
            }
            else{
                if(Operator.empty()){
                   Operator.push(arrayA[i]);
                }
                else{
                    char temp1 = Operator.pop();   //进栈前，存放运算符栈中栈顶存放字符
                    int judge = comparePriority(temp1,arrayA[i]);  //比较当前字符与栈顶字符优先级
                    if(judge == 1){           //当前字符优先级小于栈顶字符
                        int tempA = Value.pop();
                        int tempB = Value.pop();
                        int result = computeNumber(tempB,tempA,temp1);
                        Value.push(result);
                        Operator.push(arrayA[i]);
                    }
                    if(judge == 0){           //当前字符优先级大于栈顶字符
                        Operator.push(temp1);
                        Operator.push(arrayA[i]);
                    }
                    if(judge == 2){  //字符')'遇到'('，刚好使得'('出栈
                        System.out.println("'('刚好遇到')'");   //这种情况也应该不会出现，按照给定优先级，')'一般会先遇到+、-、*、/字符
                    }
                    if(judge == 3){   //此时')'刚好准备进栈
                        while(temp1 != '('){          //')'字符要等到第一个'('出栈才能结束循环
                            //System.out.println(temp1);
                            int tempA = Value.pop();
                            int tempB = Value.pop();
                            int result = computeNumber(tempB,tempA,temp1);
                            Value.push(result);
                            temp1 = Operator.pop();  
                        }
                    }
                    if(judge == -1){    //此时，说明当前栈顶字符为')'，这是不存在的，因为遇到')'，按要求不让进栈
                        System.out.println("出现栈顶有')'错误！！！");
                    }
                }
            }
        }
        
        while(!Operator.empty() && !Value.empty()){   //此时，字符栈中还存在运算符的情况
            char temp1 = Operator.pop();
            int tempA = Value.pop();
            int tempB = Value.pop();
            int result = computeNumber(tempB,tempA,temp1);
            Value.push(result);
        }
        System.out.println(Value.pop());   //此时运算符栈为空，数字栈中只存在表达式计算最终结果
    }
    //计算a operator b的值，operator = {+,-,*,/}
    public int computeNumber(int a,int b,char operator){
        int result;
        switch(operator){
        case '+': 
            result = a+b;
            break;
        case '-':
            result = a-b;
            break;
        case '*': 
            result = a*b;
            break;
        case '/': 
            result = a/b;
            break;        
        default:  
            result = 0;
            break;
        }
        return result;
    }
    //判断运算符a和b的优先级
    public int comparePriority(char a,char b){
        //使用二维数组表达运算符之间的优先级，行用字符a表示，列用字符b表示
        int[][] Value = {{1,1,0,0,0,3},
                {1,1,0,0,0,3},
                {1,1,1,1,0,3},
                {1,1,1,1,0,3},
                {0,0,0,0,0,2},
                {-1,-1,-1,-1,-1,-1}};
        int i = 0;
        int j = 0;
        if(a == '+')
            i = 0;
        if(a == '-')
            i = 1;
        if(a == '*')
            i = 2;
        if(a == '/')
            i = 3;
        if(a == '(')
            i = 4;
        if(a == ')')
            i = 5;
        
        if(b == '+')
            j = 0;
        if(b == '-')
            j = 1;
        if(b == '*')
            j = 2;
        if(b == '/')
            j = 3;
        if(b == '(')
            j = 4;
        if(b == ')')
            j = 5;
        return Value[i][j];
    }
    
    public static void main(String[] args){
        Main test = new Main(); 
        Scanner in = new Scanner(System.in);
        System.out.println("请输入一个算法表达式：");
        String A = in.nextLine();
        test.getExpressionValue(A);
    
    }
}
 
运行结果：
 
请输入一个算法表达式：
1-2+3*(4-5)
-4


请输入一个算法表达式：
1-2*((2+3)*2-(2+3))
-9


请输入一个算法表达式：
1-2*((2+3)*(2+3))
-49