c++的逆波兰运算（输出结果无$)

从键盘上输入一个算数表达式，试编写算法，计算出该表达式的逆波兰表达式。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、、/四种运算。
例1：输入为：2+3$，输出逆波兰表达式为：2 3 +。
例2：输入为：23$，输出逆波兰表达式为：2 3 。
例3：输入为：1+23$，输出逆波兰表达式为：1 2 3 * +。
例4：输入为：（1+2)3$，输出逆波兰表达式为：1 2 + 3 。
例5：输入为：（1+23）4$，输出逆波兰表达式为：1 2 3 * + 4 。
例6：输入为：6((5+(2+3)*8)+3)$，输出逆波兰表达式为：6 5 2 3 + 8 * + 3 + *。
提示1：括号成对，输出运算符；否则，输出数字。
提示2：求逆波兰表达式规则如下：设立运算数栈OPND，对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直不断运行直至表达式结束符$。（代码注释详细点）

转换逆波兰表达式的过程称为求逆波兰式。求逆波兰式的过程主要分为两个步骤：

（1）初始化两个栈：运算符栈和储存中间结果的栈。
（2）从右至左扫描表达式，将数字和字符压入两个栈。
（3）遇到运算符时，比较其与栈顶运算符的优先级：如果栈顶运算符的优先级高于当前运算符，将栈顶运算符弹出并压入中间结果栈，再次比较；如果当前运算符的优先级高于栈顶运算符，直接将当前运算符压入运算符栈。
（4）遇到括号时：如果是右括号，直接压入运算符栈。如果是左括号，则依次弹出运算符栈的运算符，并压入中间结果栈，直到遇到右括号为止，此时将这一对括号丢弃。
（5）重复步骤2至4，直到表达式最左边。
（6）将运算符栈中剩余的运算符依次弹出并压入中间结果栈。
（7）将中间结果栈中的数据依次弹出，即为逆波兰式。
在 C++ 中，可以使用栈来实现求逆波兰式的算法。栈可以使用 STL 中的 std::stack 来实现。

下面是一个实现求逆波兰式的 C++ 代码示例：

#include <iostream>
#include <stack>
#include <string>

// 定义优先级
int priority(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else {
        return 0;
    }
}

int main() {
    std::stack<char> ops;  // 运算符栈
    std::stack<int> nums;  // 中间结果栈
    std::string input;  // 输入的算数表达式
    std::cin >> input;  // 读入表达式

    // 从右至左扫描表达式
    for (int i = input.size() - 1; i >= 0; i--) {
        char c = input[i];
        if (c >= '0' && c <= '9') {
            // 如果是数字，压入中间结果栈
            nums.push(c - '0');
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            // 如果是运算符
            // 比较优先级
            while (!ops.empty() && priority(ops.top()) >= priority(c)) {
                // 如果栈顶运算符的优先级高于当前运算符，将栈顶运算符弹出并压入中间结果栈
                int num2 = nums.top();
                nums.pop();
                int num1 = nums.top();
                nums.pop();
                char op = ops.top();
                ops.pop();
                int result;
                if (op == '+') {
                    result = num1 + num2;
                } else if (op == '-') {
                    result = num1 - num2;
                } else if (op == '*') {
                    result = num1 * num2;
                } else if (op == '/') {
                    result = num1 / num2;
                }
                nums.push(result);
            }
            // 将当前运算符压入运算符栈
            ops.push(c);
        } else if (c == '(') {
            // 如果是左括号，依次弹出运算符栈的运算符，并压入中间结果栈，直到遇到右括号为止
            while (ops.top() != ')') {
                int num2 = nums.top();
                nums.pop();
                int num1 = nums.top();
                nums.pop();
                char op = ops.top();
                ops.pop();
                int result;
                if (op == '+') {
                    result = num1 + num2;
                } else if (op == '-') {
                    result = num1 - num2;
                } else if (op == '*') {
                    result = num1 * num2;
                } else if (op == '/') {
                    result = num1 / num2;
                }
                nums.push(result);
            }
            // 将左括号丢弃
            ops.pop();
        } else if (c == ')') {
            // 如果是右括号，直接压入运算符栈
            ops.push(c);
        }
    }

    // 将运算符栈中剩余的运算符依次弹出并压入中间结果栈
    while (!ops.empty()) {
        int num2 = nums.top();
        nums.pop();
        int num1 = nums.top();
        nums.pop();
        char op = ops.top();
        ops.pop();
        int result;
        if (op == '+') {
            result = num1 + num2;
        } else if (op == '-') {
            result = num1 - num2;
        } else if (op == '*') {
            result = num1 * num2;
        } else if (op == '/') {
            result = num1 / num2;
        }
        nums.push(result);
    }
    
    // 中间结果栈中的数据依次弹出即为逆波兰式
    while (!nums.empty()) {
        std::cout << nums.top() << " ";
        nums.pop();
    }
    
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define STACK_SIZE 100

// 定义运算符优先级
#define PREC_PLUS 0  // +
#define PREC_MINUS 0  // -
#define PREC_MULTIPLY 1  // *
#define PREC_DIVIDE 1  // /
#define PREC_LEFT_PAREN 1  // (
#define PREC_RIGHT_PAREN 0  // )

// 定义栈
double stack[STACK_SIZE];
int top = -1;

// 压栈
void push(double value) {
  if (top < STACK_SIZE - 1) {
    stack[++top] = value;
  } else {
    printf("Error: stack overflow\n");
    exit(EXIT_FAILURE);
  }
}

// 弹栈
double pop(void) {
  if (top >= 0) {
    return stack[top--];
  } else {
    printf("Error: stack underflow\n");
    exit(EXIT_FAILURE);
  }
}

// 返回运算符优先级
int get_precedence(char operator) {
  switch (operator) {
    case '+':
      return PREC_PLUS;
    case '-':
      return PREC_MINUS;
    case '*':
      return PREC_MULTIPLY;
    case '/':
      return PREC_DIVIDE;
    case '(':
      return PREC_LEFT_PAREN;
    case ')':
      return PREC_RIGHT_PAREN;
    default:
      printf("Error: invalid operator\n");
      exit(EXIT_FAILURE);
  }
}

// 计算两个数的运算结果
double calculate(double operand1, char operator, double operand2) {
  switch (operator) {
    case '+':
      return operand1 + operand2;
    case '-':
      return operand1
}
int main() {
  // 定义表达式字符串和计算结果变量
  char expression[100];
  double result;

  // 读入表达式字符串
  printf("Enter an expression: ");
  scanf("%s", expression);

  // 调用函数计算逆波兰表达式的结果
  result = calculate_rpn(expression);

  // 输出结果
  printf("Result: %f\n", result);

  return 0;
}

#include<iostream>
#include<sstream>
#include<stack>
#include<vector>
#include<map>

using namespace std;




int IsOper(char str, const vector<char> &oper) {
    for (int i = 0; i < oper.size(); i++) {
        if (oper[i] == str) return i;
    }
    return -1;
}

void Excharge(stack<char> &s2, stack<char> &s1) {
    while (!s2.empty()) {
        s1.push(s2.top());
        s2.pop();
    }
}

void Excharge_(stack<char>& s2, stack<char>& s1) {
    while (!s2.empty() && s2.top() != '(') {
        s1.push(s2.top());
        s2.pop();
    }
    if (s2.empty()) return;
    s2.pop();
}

void Show(stack<char> s1) {

    if (s1.empty()) {
        cout << endl;
        return;
    }
    char val = s1.top();
    s1.pop();
    Show(s1);
    cout << val;  
}

void ReversePolish(string expression) {
    stack<char> s1;
    stack<char> s2;
    vector<char> oper = { '*','/','+','-','(',')' };
    map<char, int> rank;
    rank['('] = 3;
    rank['*'] = 2;
    rank['/'] = 2;
    rank['+'] = 1;
    rank['-'] = 1;
    for (int i = 0; i < expression.size(); i++) {
        int ret = IsOper(expression[i], oper);
        if (ret < 0) {
            s1.push(expression[i]);   //压入栈内
        }
        else {
            if (s2.empty() || s2.top() == '(') {
                s2.push(expression[i]);
            }
            else if (expression[i] == ')') {
                Excharge_(s2, s1);
            }
            else if (rank[expression[i]] > rank[s2.top()]) {
                s2.push(expression[i]);
            }
            else {
                Excharge(s2, s1);
                s2.push(expression[i]);   // 栈为空，直接压入s2
            }
        }
    }
    Excharge(s2, s1);
    Show(s1);
}

int main(void) {

    ReversePolish("(1+2)*5");
    ReversePolish("1+2*5");
    ReversePolish("(a+b)*c+d-(e+g)*h");

    return 0;
}

提供参考实例【C++逆波兰式转化成中缀表达式，并输出最终计算结果】，链接：https://www.cnblogs.com/pcwlcsm/p/15146986.html

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define STACK_SIZE 100

// 定义运算符优先级
#define PREC_PLUS 0  // +
#define PREC_MINUS 0  // -
#define PREC_MULTIPLY 1  // *
#define PREC_DIVIDE 1  // /
#define PREC_LEFT_PAREN 1  // (
#define PREC_RIGHT_PAREN 0  // )

// 定义栈
double stack[STACK_SIZE];
int top = -1;

// 压栈
void push(double value) {
  if (top < STACK_SIZE - 1) {
    stack[++top] = value;
  } else {
    printf("Error: stack overflow\n");
    exit(EXIT_FAILURE);
  }
}

// 弹栈
double pop(void) {
  if (top >= 0) {
    return stack[top--];
  } else {
    printf("Error: stack underflow\n");
    exit(EXIT_FAILURE);
  }
}

// 返回运算符优先级
int get_precedence(char operator) {
  switch (operator) {
    case '+':
      return PREC_PLUS;
    case '-':
      return PREC_MINUS;
    case '*':
      return PREC_MULTIPLY;
    case '/':
      return PREC_DIVIDE;
    case '(':
      return PREC_LEFT_PAREN;
    case ')':
      return PREC_RIGHT_PAREN;
    default:
      printf("Error: invalid operator\n");
      exit(EXIT_FAILURE);
  }
}

// 计算两个数的运算结果
double calculate(double operand1, char operator, double operand2) {
  switch (operator) {
    case '+':
      return operand1 + operand2;
    case '-':
      return operand1
}
int main() {
  // 定义表达式字符串和计算结果变量
  char expression[100];
  double result;

  // 读入表达式字符串
  printf("Enter an expression: ");
  scanf("%s", expression);

  // 调用函数计算逆波兰表达式的结果
  result = calculate_rpn(expression);

  // 输出结果
  printf("result: %f\n", result);

  return 0;
}

整行读入，先将括号里的视为整体，找到运算符并移到右边，然后处理括号里的部分，重复这一过程，直到找不到括号为止。
c代码：

#include<stdio.h>
#include<string.h>

//返回与第一个左括号配对的右括号的地址
char * BracketMatch(const char * str) {
    int count = 1;    //未配对的左括号个数
    str = strchr(str, '(');
    if (str) {
        //如果找到左括号，寻找配对的右括号，当未配对括号个数为0时，就找到了配对的右括号
        while (count && *str++) {
            if (*str == '(')count++;
            else if (*str == ')')count--;
        }
        if (count)    //没有配对的右括号
            return NULL;
        else
            return (char*)str;    //如果是c++程序，这一句改成“return const_cast<char*>str;”
    } else {
        //没有左括号
        return NULL;
    }
}

//将left和right确定的一段字符的指定运算符移到右边，不处理括号里的内容，仅交换位置，不改变字符串。
//这段字符需要经过预处理，否则会出错。signs必须是同级的，且从高到低调用
//lsigns指向优先级不高于sign的运算符，如果有需要，改一下逻辑，用空格作为分隔，可以不用这个参数
void convert(char *left, char *right, const char * signs, const char *lsigns) {
    char *i, *j, t;
    //i遍历这段字符
    for (i = left; i != right; i++) {
        if (*i == '(') {
            //如果*i是左括号，则找到配对的右括号，并将括号以及括号里的内容复制到dest里
            j = BracketMatch(i);
            if (!j)return;    //表达式有误，括号不成对
            while (i != j)*left++ = *i++;
            *left++ = *i;    //括号也复制
        } else if (strchr(signs, *i)) {
            //如果*i是指定的运算符，则将运算符后面的，直至下一个运算符（跳过括号）或结束为止的部分复制（忽略左边的空格），再将运算符放在最后（加一个空格）
            t = *i;
            for (i = i + 2; i != right && !strchr(lsigns, *i); i++) {
                if (*i == '(') {
                    j = BracketMatch(i);
                    if (!j)return;    //表达式有误，括号不成对
                    while (i != j)*left++ = *i++;
                }
                *left++ = *i;
            }
            if (i == right) {
                *left++ = ' ';
                *left++ = t;
            } else {
                *left++ = t;
                *left++ = ' ';
            }
            i--;
        } else {
            //不是括号也不是运算符，直接复制
            *left++ = *i;
        }
    }
}

//预处理，删'$'，运算符前后加空格
void expressionPreTreatment(char * str, const char*operators) {
    //删'$'，r移到str右端
    char *l, *r;
    r = strchr(str, '$');
    if (r) {
        *r = '\0';
    } else {
        r = str + strlen(str);
    }
    char temp[(r - str) * 2], *t = temp;    //2倍一般够了
    //遍历，找到运算符就加空格（如果已经有空格就不加了）
    for (l = str; l != r; l++) {
        if (strchr(operators, *l)) {
            if (l[-1] != ' ')*t++ = ' ';
            *t++ = *l;
            if (l[1] != ' ')*t++ = ' ';
        } else {
            *t++ = *l;
        }
    }
    *t = '\0';
    strcpy(str, temp);
}

int main() {
    char expression[1000];
    char *l, *r;//l和r分别指向表达式或子表达式（括号里的内容视为子表达式）的左右两端
    printf("输入为：");
    gets(expression);
    expressionPreTreatment(expression, "+-*/");
    l = expression;
    r = l + strlen(l);
    while (1) {
        convert(l, r, "*/", "+-*/");
        convert(l, r, "+-", "+-");
        l = strchr(l, '(');
        if (l) {
            r = BracketMatch(l);
            l++;
        } else {
            break;
        }
    }
    //去掉括号
    for (l = r = expression; *r; r++) {
        if (*r != '(' && *r != ')')*l++ = *r;
    }
    *l = '\0';
    printf("输出为：%s\n", expression);
    return 0;
}

运行结果（临时套了个死循环）

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h> 
#include<assert.h>

#define INITSIZE  20
#define INCREMENT 10
#define MAXBUFFER 20
#define LEN  sizeof(Elemtype)

/*栈的动态分配存储结构*/ 
typedef char Elemtype;
typedef struct{
    Elemtype *base;
    Elemtype *top;
    int StackSize;
}SqStack;

/*初始化栈*/
void InitStack(SqStack *S)
{
    S->base=(Elemtype*)malloc(LEN*INITSIZE);
    assert(S->base !=NULL);
    S->top=S->base;
    S->StackSize=INITSIZE;
}

/*压栈操作*/ 
void PushStack(SqStack *S,Elemtype c)
{
    if(S->top - S->base >= S->StackSize)
    {
        S->base=(Elemtype*)realloc(S->base,LEN*(S->StackSize+INCREMENT));
        assert(S->base !=NULL);
        S->top =S->base+S->StackSize;
        S->StackSize+=INCREMENT;
    }
    *S->top++ = c;
}
/*求栈长*/
int StackLength(SqStack *S)
{
    return (S->top - S->base);
}
/*弹栈操作*/
int PopStack(SqStack *S,Elemtype *c)
{
    if(!StackLength(S))
    {
        return 0;
    }
    *c=*--S->top;
    return 1;
}

/*中缀转后缀函数*/
int Change(SqStack *S,Elemtype str[])
{
    int i=0;
    Elemtype e;
    InitStack(S);
    while(str[i]!='\0')
    {
        while(isdigit(str[i])) 
        {/*过滤数字字符，直接输出，直到下一位不是数字字符打印空格跳出循环 */
            printf("%c",str[i++]);
            if(!isdigit(str[i]))
            {
                printf(" ");
            }
        }
        /*加减运算符优先级最低，如果栈顶元素为空则直接入栈，否则将栈中存储
          的运算符全部弹栈，如果遇到左括号则停止，将弹出的左括号从新压栈，因为左
          括号要和又括号匹配时弹出，这个后面单独讨论。弹出后将优先级低的运算符压入栈中*/
        if(str[i]=='+'||str[i]=='-')
        {
            if(!StackLength(S))
            {
                PushStack(S,str[i]);
            }
            else
            {
                do
                {
                    PopStack(S,&e);
                    if(e=='(')
                    {
                        PushStack(S,e);
                    }
                    else
                    {
                        printf("%c ",e);
                    }
                }while( StackLength(S) && e != '(' );
                
                PushStack(S,str[i]);
            }
        }
        /*当遇到右括号是，把括号里剩余的运算符弹出，直到匹配到左括号为止
          左括号只弹出不打印（右括号也不压栈）*/
        else if(str[i]==')')
        {
            PopStack(S,&e);
            while(e!='(')
            {
                printf("%c ",e);
                PopStack(S,&e);
            }
        }
        /*乘、除、左括号都是优先级高的，直接压栈*/
        else if(str[i]=='*'||str[i]=='/'||str[i]=='(')
        {
            PushStack(S,str[i]);
        }
        
        else if(str[i]=='\0')
        {
            break;
        }
        
        else if(str[i]=='$'){
            while(StackLength(S))
            {
                PopStack(S,&e);
                printf("%c ",e);
            }
            return 0;
        }
        else
        {
            printf("\n输入格式错误！\n");
            return 0;
        }
        i++;
    }
    /*最后把栈中剩余的运算符依次弹栈打印*/
}

int main()
{
    Elemtype str[MAXBUFFER];
    SqStack S;
    gets(str);
    Change(&S,str);
    
    getchar();
    getchar();
    return 0;
}

参考：

#include <iostream>
#include <stack>
#include <cctype>

using namespace std;

int main() {
    stack<int> opnd;  // 运算数栈
    stack<char> optr;  // 运算符栈
    char c;
    while (cin >> c && c != '$') {
        if (isdigit(c)) {
            // 输出数字
            cout << c << ' ';
        } else {
            // 更新运算符栈
            while (!optr.empty() && optr.top() != '(' && (optr.top() == '*' || optr.top() == '/' || (optr.top() == '+' || optr.top() == '-'))) {
                // 弹出两个运算数和一个运算符
                int b = opnd.top(); opnd.pop();
                int a = opnd.top(); opnd.pop();
                char op = optr.top(); optr.pop();
                // 输出运算符
                cout << a << ' ' << b << ' ' << op << ' ';
            }
            optr.push(c);  // 压入新运算符
        }
    }
    // 输出剩余的运算符
    while (!optr.empty()) {
        // 弹出两个运算数和一个运算符
        int b = opnd.top(); opnd.pop();
        int a = opnd.top(); opnd.pop();
        char op = optr.top(); optr.pop();
        // 输出运算符
        cout << a << ' ' << b << ' ' << op << ' ';
    }
    cout << endl;
    return 0;
}

#include <iostream>
#include <stack>
#include <string>

// 定义运算符优先级
const int PRIORITY[4] = {0, 1, 1, 2};

// 将字符转化为对应的数字
int charToInt(char c) {
    switch (c) {
        case '+': return 1;
        case '-': return 2;
        case '*': return 3;
        case '/': return 4;
        default: return 0;
    }
}

int main() {
    std::string expr; // 存储输入的表达式
    std::stack<int> opnd; // 运算数栈
    std::stack<char> optr; // 运算符栈

    std::cout << "输入算数表达式（以$结束）：" << std::endl;
    std::cin >> expr;

    for (int i = 0; i < expr.length(); i++) {
        char c = expr[i];
        if (c == '$') break; // 结束输入

        // 如果是数字，则压入运算数栈
        if (c >= '0' && c <= '9') {
            opnd.push(c - '0');
        }
        // 如果是运算符
        else {
            // 如果是左括号，则压入运算符栈
            if (c == '(') {
                optr.push(c);
            }
            // 如果是右括号，则将运算符栈中的运算符依次弹出并输出，直到遇到左括号为止
            else if (c == ')') {
                while (optr.top() != '(') {
                    std::cout << optr.top() << " ";
                    optr.pop();
                }
                optr.pop(); // 弹出左括号
            }
           
            // 如果是运算符，则依次将运算符栈中的运算符弹出并输出，直到遇到优先级更低或者栈为空为止
            else {
                int currPriority = PRIORITY[charToInt(c)];
                while (!optr.empty() && PRIORITY[charToInt(optr.top())] >= currPriority) {
                    std::cout << optr.top() << " ";
                    optr.pop();
                }
                optr.push(c);
            }
        }
    }

    // 将运算符栈中剩余的运算符依次弹出并输出
    while (!optr.empty()) {
        std::cout << optr.top() << " ";
        optr.pop();
    }

    return 0;
}