fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <cstring>
  4. #include <stack>
  5. #include <math.h>
  6.  
  7. using namespace std;
  8.  
  9. typedef double ElemType;
  10. const int MaxSize = 100;
  11. const int inf = 0x3f3f3f3f;
  12.  
  13. void trans(char *exp, char postexp[]);
  14. double compvalue(char *postexp);
  15.  
  16. void filter(char * dest, char * src, char ch)
  17. {
  18.     int cur = 0;
  19.     int i = 0; 
  20.     while (src[i++] != '\0')
  21.     {
  22.     	if (src[i - 1] == ch) continue;
  23.     	dest[cur++] = src[i - 1];
  24.     }
  25.     dest[cur] = '\0';
  26. }
  27.  
  28. int main(void)
  29. {
  30.     char exp[MaxSize];
  31.     char postexp[MaxSize];
  32. 	char postexp1[MaxSize];
  33.     cout << "enter the infix expression." << endl;
  34.  
  35.     scanf("%[^\n]", exp);
  36. 	//strcpy(exp, "(6 + 2) * 5 - 8 / 4");
  37.  
  38. 	filter(exp, exp, ' ');
  39.     printf("the original infix expression is\n%s\n", exp);
  40.     trans(exp, postexp);
  41. 	filter(postexp1, postexp, '#');
  42.     cout << "the expression in postfix notation is:" << endl << postexp1 << endl;
  43.     cout << "the value is:" << compvalue(postexp) << endl;
  44.  
  45.  
  46.     return 0;
  47. }
  48.  
  49. void printstack(stack<char> Optr)
  50. {
  51. 	stack<char> temp;
  52. 	printf("the stack is:");
  53. 	if (Optr.empty())
  54. 	{
  55. 		printf("empty\n");
  56. 		return;
  57. 	}
  58. 	while (!Optr.empty())
  59. 	{
  60. 		temp.push(Optr.top());
  61. 		Optr.pop();
  62. 	}
  63.  
  64. 	while (!temp.empty())
  65. 	{
  66. 		char c = temp.top();
  67. 		temp.pop();
  68. 		printf("%c ", c);
  69. 		Optr.push(c);
  70. 	}
  71. 	printf("\n");
  72. }
  73.  
  74. void trans(char *exp, char postexp[])
  75. {
  76.     stack<char> Optr;
  77.     int i = 0;
  78.     char e;
  79.     while (*exp != '\0')
  80.     {
  81.         switch (*exp)
  82.         {
  83.             case '(':
  84.                 Optr.push(*exp);
  85. 				printstack(Optr);
  86.                 exp++;
  87.                 break;
  88.             case ')':
  89.                 e = Optr.top();
  90.                 Optr.pop();
  91. 				printstack(Optr);
  92.                 while (e != '(')
  93.                 {
  94.                     postexp[i++] = e;
  95.                     e = Optr.top();
  96.                     Optr.pop();
  97. 					printstack(Optr);
  98.                 }
  99.                 exp++;
  100.                 break;
  101.             case '+':
  102.             case '-':
  103.                 while (!Optr.empty())
  104.                 {
  105.                     if (Optr.top() != '(')
  106.                     {
  107.                         e = Optr.top();
  108.                         postexp[i++] = e;
  109.                         Optr.pop();
  110. 						printstack(Optr);
  111.                     }
  112.                     else
  113.                         break;
  114.                 }
  115.                 Optr.push(*exp);
  116. 				printstack(Optr);
  117.                 exp++;
  118.                 break;
  119.             case '*':
  120.             case '/':
  121. 			case '%':
  122. 			case '^':
  123.                 while (!Optr.empty())
  124.                 {
  125.                     if (Optr.top() == '*' || Optr.top() == '/' || Optr.top() == '%' || Optr.top() == '^')
  126.                     {
  127.                         e = Optr.top();
  128.                         postexp[i++] = e;
  129.                         Optr.pop();
  130. 						printstack(Optr);
  131.                     }
  132.                     else
  133.                         break;
  134.                 }
  135.                 Optr.push(*exp);
  136. 				printstack(Optr);
  137.                 exp++;
  138.                 break;
  139.             default:
  140.                 while (*exp >= '0' && *exp <= '9')
  141.                 {
  142.                     postexp[i++] = *exp;
  143.                     exp++;
  144.                 }
  145.                 postexp[i++] = '#';
  146.         }
  147.     }
  148.     while (!Optr.empty())
  149.     {
  150.         e = Optr.top();
  151.         postexp[i++] = e;
  152.         Optr.pop();
  153. 		printstack(Optr);
  154.     }
  155.     postexp[i] = '\0';
  156. }
  157.  
  158. double compvalue(char *postexp)
  159. {
  160.     double d, a, b, c, e;
  161.     stack<double> Opnd;
  162.     while (*postexp != '\0')
  163.     {
  164.         switch (*postexp)
  165.         {
  166.             case '+':
  167.                 b = Opnd.top();
  168.                 Opnd.pop();
  169.                 a = Opnd.top();
  170.                 Opnd.pop();
  171.                 c = a+b;
  172.                 Opnd.push(c);
  173.                 break;
  174.             case '-':
  175.                 b = Opnd.top();
  176.                 Opnd.pop();
  177.                 a = Opnd.top();
  178.                 Opnd.pop();
  179.                 c = a-b;
  180.                 Opnd.push(c);
  181.                 break;
  182.             case '*':
  183.                 b = Opnd.top();
  184.                 Opnd.pop();
  185.                 a = Opnd.top();
  186.                 Opnd.pop();
  187.                 c = a*b;
  188.                 Opnd.push(c);
  189.                 break;
  190.             case '/':
  191.                 b = Opnd.top();
  192.                 Opnd.pop();
  193.                 a = Opnd.top();
  194.                 Opnd.pop();
  195.                 if (b == 0)
  196.                 {
  197.                     cout << "divide by zero!" << endl;
  198.                     return inf;
  199.                 }
  200.                 else
  201.                 {
  202. 					c = a/b;
  203.                     Opnd.push(c);
  204.                 }
  205.                 break;
  206. 			case '%':
  207.                 b = Opnd.top();
  208.                 Opnd.pop();
  209.                 a = Opnd.top();
  210.                 Opnd.pop();
  211.                 if (b == 0)
  212.                 {
  213.                     cout << "divide by zero!" << endl;
  214.                     return inf;
  215.                 }
  216.                 else
  217.                 {
  218.                     c = (int)a%(int)b;
  219.                     Opnd.push(c);
  220.                 }
  221.                 break;
  222. 			case '^':
  223.                 b = Opnd.top();
  224.                 Opnd.pop();
  225.                 a = Opnd.top();
  226.                 Opnd.pop();
  227.                 c = pow(a,b);
  228.                 Opnd.push(c);
  229.                 break;
  230.             default:
  231.                 d = 0;
  232.                 while (*postexp >= '0' && *postexp <= '9')
  233.                 {
  234.                     d = d*10+*postexp-'0';
  235.                     postexp++;
  236.                 }
  237.                 Opnd.push(d);
  238.                 break;
  239.         }
  240.         postexp++;
  241.     }
  242.     e = Opnd.top();
  243.     Opnd.pop();
  244.     return e;
  245. }
Success #stdin #stdout 0s 4484KB
comments (?)
stdin
copy 
(6 + 2) * 5 - 8 / 4
stdout
copy 
enter the infix expression.
the original infix expression is
(6+2)*5-8/4
the stack is:( 
the stack is:( + 
the stack is:( 
the stack is:empty
the stack is:* 
the stack is:empty
the stack is:- 
the stack is:- / 
the stack is:- 
the stack is:empty
the expression in postfix notation is:
62+5*84/-
the value is:38
https://ideone.com/50QE83
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!